《利用JAVA实现数据结构中常用的插入排序和快速排序算法.doc》由会员分享，可在线阅读，更多相关《利用JAVA实现数据结构中常用的插入排序和快速排序算法.doc（12页珍藏版）》请在金锄头文库上搜索。
1、利用JAVA实现数据结构中常用的插入排序和快速排序算法 在网上看的，挺全的，收了先。第十章 排序源程序：Data.javapackage Sort;class Data Comparable key; Object value; public Data() public Data(Data data) this.key=data.key; this.value=data.value; public Data(Comparable key,Object value) this.key=key; this.value=value; public String toString() return k
2、ey=+key+;+value=+value+;+n; Insertion.javapackage Sort;public class InsertionSort public InsertionSort() /直接插入排序,从下标1开始 public static void straightInsertionSort(Data data) int i, j; for (i = 2; i data.length; i+) if (pareTo(datai - 1.key) 0) data0 = datai;/复制为监视哨 for (j = i - 1; pareTo(dataj.key) 0;
3、 -j) dataj + 1 = dataj;/记录右移 dataj + 1 = data0;/插入 /折半插入排序,从下标1开始 public static void BinaryInsertionSort(Data data) int i,j,low,high,mid; for(i=2;idata.length;i+) if (pareTo(datai - 1.key) 0) data0=datai; /找插入位置 low=1;high=i-1; while(low=high) mid =(low+high)/2; if(pareTo(datamid.key)=high+1;j-) dat
4、aj+1=dataj; datahigh+1=data0;/插入 /表插入排序 public static void ListInsertionSort(Data data) int i,j,k; /inner class:Table class Table Comparable key; int next; Table table=new Tabledata.length; for(i=1;idata.length;i+) tablei=new Table(); tablei.key=datai.key; table0=new Table(); table0.key=new Integer(
5、Integer.MAX_VALUE); table0.next=1; table1.next=0; for(i=2;idata.length;i+) for(j=0,k=table0.next;pareTo(tablei.key)=0;j=k,k=tablek.next); tablej.next=i; tablei.next=k; Data newData=new Datadata.length; int position=table0.next; for(i=1;idata.length;i+) newDatai=dataposition; position=tableposition.n
6、ext; /data=newData;/不知为什么不能把newData赋给data，而必须用下面的 for(i=1;i 1) lastChangeIndex = 1; for (j = 1; j i; j+) if (dataj + pareTo(dataj.key) 0) temp = dataj + 1; dataj + 1 = dataj; dataj = temp; lastChangeIndex = j; i = lastChangeIndex; /快速排序 public static void QuickSort(Data data) QSort(data, 1, data.len
7、gth - 1); public static void OptimizeQuickSort(Data data) OQSort(data,1,data.length-1); private static void QSort(Data data, int s, int t) int pivotLoc; if (s t) pivotLoc = Partition(data, s, t); /对data1.data.length-1进行一次划分 QSort(data, s, pivotLoc - 1); /对低子序列进行递归排序 QSort(data, pivotLoc + 1, t); /对高
8、子序列进行递归排序 private static void OQSort(Data data,int s,int t) int pivotLoc; if(st) pivotLoc=RandomPartition(data,s,t); QSort(data, s, pivotLoc - 1); /对低子序列进行递归排序 QSort(data, pivotLoc + 1, t); /对高子序列进行递归排序 private static int RandomPartition(Data data,int low,int high) /i是low int i=(int)Math.random()*(h
9、igh-low)+low; Data temp=datalow; datalow=datai; datai=temp; return Partition(data,low,high); private static int Partition(Data data, int low, int high) Comparable pivotKey; data0 = datalow; pivotKey = datalow.key; /枢轴 while (low high) while (low = 0) high-; datalow = datahigh; while (low high & pareTo(pivotKey) 0; i-) HeapAdjust(data, i, data.length-1); /建立大顶堆 for (i = (data.length - 1); i 1; i-) temp = data1; data1 = datai; datai = temp; HeapAdjust(data, 1, i - 1); private static void HeapAdjust(Data data, int start, int end) int j; Data temp; temp = datastart; for
