數(shù)據(jù)結構課程設計之java排序

1、WORD格式"數(shù)據(jù)構造課程設計"專業(yè)資料整理WORD格式專業(yè) : 計算機科學與技術*：周兵學號 :030940122專業(yè)資料整理WORD格式一、需求分析一、設計代碼：1. 直接插入排序：專業(yè)資料整理WORD格式publicclassInsertSort publicstatic<T extendsComparable<"superT>> voidinsertSort(T array) for( inti = 1; i <= array.length- 1; i+) intj = i;while(j>=1 && a

2、rrayjpareTo(arrayj - 1) < 0) T temp = arrayj;arrayj = arrayj - 1;arrayj - 1 = temp;insertSort(T專業(yè)資料整理WORD格式j-;publicstaticvoid main(String args) Integer testArray = 23, 25, 12, 42, 35,33,43,57;System.out.println(" 排序前 :");for(Integer item : testArray) System.out.print(item);System.out.p

3、rint(' ');System.out.println();System.out.println("-");InsertSort.insertSort(testArray);System.out.println(" 排序后 :");for(Integer item : testArray) System.out.print(item);System.out.print(' ');實驗結果：專業(yè)資料整理WORD格式2. 折半插入排序：public class BInsertSort public static void b

4、InsertSort(int temp) int length = temp.length;for (int i = 1; i < length; i+) int tempVal = tempi;int low = 0;int high = i - 1;while (low <= high) int middle = (low + high) / 2;if (tempVal < tempmiddle)high = middle - 1;elselow = middle + 1;for (int j = i; j > high + 1; j-)tempj = tempj

5、- 1;temphigh + 1 = tempVal;public static void main(String args) int a = 5, 1, 76, 2, 4, 84, 36, 22, 62, 90 ;bInsertSort(a);System.out.println("排序后 :");for (int i = 0; i < a.length; i+)System.out.print(ai + " ");實驗結果：專業(yè)資料整理WORD格式3. 希爾排序 :publicclassInsertionSort 專業(yè)資料整理WORD格式pub

6、licintforvoidshellInertionSort(double sorted,intsortedLen= sorted.length;( intj=inc+1;j<sortedLen;j+ )if(sortedj<sortedj-inc)sorted0= sortedj;/先保存一下后面的那個intinsertPos=j;for( intk=j-inc;k>=0;k-=inc)if(sortedk>sorted0)sortedk+inc=sortedk;if(k-inc<=0)insertPos = k;inc)專業(yè)資料整理WORD格式專業(yè)資料整理WO

7、RD格式elseinsertPos=k+inc;break;專業(yè)資料整理WORD格式專業(yè)資料整理WORD格式sortedinsertPos=sorted0;publicvoidshellInsertionSort(double sorted)int incs=7,5,3,1;專業(yè)資料整理WORD格式intnum= incs.length;專業(yè)資料整理WORD格式intinc=0;專業(yè)資料整理WORD格式for( intj=0;j<num;j+)inc= incsj;shellInertionSort(sorted,inc);專業(yè)資料整理WORD格式專業(yè)資料整理WORD格式publicst

8、aticvoidmain(String args) 專業(yè)資料整理WORD格式Random random=new Random(6);intarraysize= 21;double sorted=newdoublearraysize;System.out .print("Before Sort:");for( intj=1;j<arraysize;j+)sortedj= (int)(random.nextDouble()* 100);System.out .print(int)sortedj+" ");專業(yè)資料整理WORD格式System.out .

9、println();InsertionSort sorter=new InsertionSort();sorter.shellInsertionSort(sorted);System.out .print("After Sort:");for( intj=1;j<sorted.length;j+)System.out .print(int)sortedj+" ");專業(yè)資料整理WORD格式專業(yè)資料整理WORD格式System.out .println();專業(yè)資料整理WORD格式專業(yè)資料整理WORD格式實驗結果：4. 冒泡排序：專業(yè)資料整理WORD

10、格式publicclassBubbluSort 專業(yè)資料整理WORD格式publicstaticvoidsortiere(booleanunsortiert =inttemp;while(unsortiert) trueint x) ;專業(yè)資料整理WORD格式unsortiert =falsefor( inti = 0; i < x.if(xi > xi + 1) temp = xi;xi = xi + 1;length- 1; i+)專業(yè)資料整理WORD格式xi + 1 = temp;專業(yè)資料整理WORD格式unsortiert =true;專業(yè)資料整理WORD格式publics

11、taticvoid main(String args) int liste = 0, 9, 4, 6, 2, 8, 5, 1, 7, 3 ;System.out.println(" 排序前： " );for( inti = 0; i < liste.length; i+)System.out .print(listei +" ");System.out.println();System.out.println("-");System.out.println(" 排序后： " );sortiere(liste)

12、;for( inti = 0; i < liste.length; i+)System.out .print(listei +" ");實驗結果：5. 快速排序：publicclassExchangeSort 專業(yè)資料整理WORD格式publicvoidQuickExchangeSortBackTrack(double sorted,專業(yè)資料整理WORD格式intlow,inthigh) if(low < high) intpivot = findPivot(sorted, low, high);專業(yè)資料整理WORD格式QuickExchangeSortBack

13、Track(sorted, low, pivot - 1);QuickExchangeSortBackTrack(sorted, pivot + 1, high);專業(yè)資料整理WORD格式publicintfindPivot(sorted0 = sortedlow;double sorted,intlow,inthigh) 專業(yè)資料整理WORD格式while(low < high) while(low < high && sortedhigh >= sorted0)-high;sortedlow = sortedhigh;while(low < high

14、 && sortedlow <= sorted0)+low;sortedhigh = sortedlow;sortedlow = sorted0;returnlow;publicstaticvoid main(String args) Random random =new Random(6);intarraysize = 10;double sorted =new doublearraysize;System.out.println(" 排序前 :");for(intj = 1; j < arraysize; j+) sortedj = (int

15、) (random.nextDouble() * 100);System.out.print(int) sortedj +" ");System.out.println();System.out.println("-");ExchangeSort sorter =new ExchangeSort();sorter.QuickExchangeSortBackTrack(sorted, 1,arraysize - 1);System.out.println(" 排序后 :");for(intj = 1; j < sorted.len

16、gth; j+) System.out.print(int) sortedj +" ");System.out.println();實驗結果：6. 直接選擇排序：專業(yè)資料整理WORD格式publicclassSelectionSort 專業(yè)資料整理WORD格式publicvoidstraitSelectionSort(intsortedLen= sorted.lengthfor( intj=1;j<sortedLen;j+)intjMin= getMinIndex(sorted,j);double sorted)專業(yè)資料整理WORD格式exchange(sorted,

17、j,jMin);專業(yè)資料整理WORD格式publicvoidexchange(double sorted,intintsortedLen= sorted.length;if(i<sortedLen && j<sortedLen && i<j && i>=0 && j>=0)doubletemp= sortedi;i,intj)專業(yè)資料整理WORD格式sortedi=sortedj;sortedj=temp;專業(yè)資料整理WORD格式publicintgetMinIndex(double sorted,i

18、ntsortedLen= sorted.length;intminJ=1;doublemin= Double.MAX_VALUE;for( intj=i;j<sortedLen;j+)if(sortedj<min)min= sortedj;minJ= j;inti)專業(yè)資料整理WORD格式專業(yè)資料整理WORD格式returnminJ;專業(yè)資料整理WORD格式publicstaticvoidmain(String args)Random random=new Random(6);intarraysize=9;double sorted=newdoublearraysize;Syste

19、m.out .println(" 排序前 :" );for( intj=1;j<arraysize;j+)sortedj= (int)(random.nextDouble()* 100);System.out .print(int)sortedj+" ");System.out .println();專業(yè)資料整理WORD格式System. out .println( SelectionSort sorter="-"new SelectionSort(););專業(yè)資料整理WORD格式sorter.straitSelectionSo

20、rt(sorted);專業(yè)資料整理WORD格式System.for( intSystem.out .println(j=1;j<sorted.out .print("排序后 :" );length;j+)int)sortedj+"");專業(yè)資料整理WORD格式專業(yè)資料整理WORD格式System.out .println();專業(yè)資料整理WORD格式實驗結果：7. 堆排序：專業(yè)資料整理WORD格式publicclassSelectionSort 專業(yè)資料整理WORD格式publicifvoidheapAdjust(double sorted,int

21、(start<end)doubletemp= sortedstart;for( intj=2*start;j<end;j *=2)if(j+1<end && sortedj-sortedj+1>10e-6)start,intend)專業(yè)資料整理WORD格式+j;專業(yè)資料整理WORD格式if(temp<=sortedj)break;專業(yè)資料整理WORD格式sortedstart=sortedj;start=j;sortedstart=temp;專業(yè)資料整理WORD格式publicintifvoidexchange(double sorted,ints

22、ortedLen= sorted.length;(i<sortedLen && j<sortedLen && i<j && i>=0 && j>=0)i,intj)專業(yè)資料整理WORD格式doubletemp= sortedi;sortedi=sortedj;sortedj=temp;專業(yè)資料整理WORD格式publicvoid heapSelectionSort( int sortedLen = sorted.double length ; sorted)專業(yè)資料整理WORD格式for( inti=

23、sortedLen/2;i>0;i-)專業(yè)資料整理WORD格式heapAdjust(sorted,i,sortedLen);for( inti=sortedLen;i>1;-i)exchange(sorted,1,i);heapAdjust(sorted,1,i-1);publicstaticvoidmain(String args)Random random=new Random(6);intarraysize=10;double sorted=new doublearraysize;System.out.println(" 排序前 :");for( intj

24、=1;j<arraysize;j+)sortedj= (int)(random.nextDouble()* 100);System.out.print(int)sortedj+" ");System.out.println();System.out.println("-");SelectionSort sorter=newSelectionSort();sorter.heapSelectionSort(sorted);System.out.println(" 排序后 :");for( intj=1;j<sorted.len

25、gth;j+)System.out.print(int)sortedj+" ");System.out.println();實驗結果：專業(yè)資料整理WORD格式8. 歸并排序 :專業(yè)資料整理WORD格式publicclassMergeSort 專業(yè)資料整理WORD格式privatedoublebridge; /輔助數(shù)組專業(yè)資料整理WORD格式publicifvoid (obj = throwsort(nullnewdouble obj)NullPointerException("Theparamcannotbe專業(yè)資料整理WORD格式null!");專業(yè)資

26、料整理WORD格式專業(yè)資料整理WORD格式bridge=newdoublemergeSort(obj, 0, obj.bridge=null;obj.length length;- 1);/初始化中間數(shù)組/歸并排序?qū)I(yè)資料整理WORD格式專業(yè)資料整理WORD格式privatevoidmergeSort(doubleif(left < right)intcenter = (left + right) / 2;mergeSort(obj, left, center);mergeSort(obj, center + 1, right);merge(obj, left, center, righ

27、t); obj,intleft,intright)專業(yè)資料整理WORD格式專業(yè)資料整理WORD格式privateintintintwhilevoidmerge(doubleobj,intmid = center + 1;third = left;tmp = left;(left <= center && mid <= right)if(objleft-objmid<=10e-6)bridgethird+ = objleft+;elsebridgethird+ = objmid+;left,intcenter,intright)專業(yè)資料整理WORD格式專業(yè)資料整

28、理WORD格式while(mid <= right)專業(yè)資料整理WORD格式bridgethird+ = objmid+;專業(yè)資料整理WORD格式專業(yè)資料整理WORD格式while(left <= center)bridgethird+ = objleft+;專業(yè)資料整理WORD格式專業(yè)資料整理WORD格式/ 將中間數(shù)組的內(nèi)容拷貝回原數(shù)組copy(obj, tmp, right);專業(yè)資料整理WORD格式privatevoidcopy(while(left <= right)objleft =left+;doublebridge obj,left;intleft,intrig

29、ht)專業(yè)資料整理WORD格式專業(yè)資料整理WORD格式publicstaticvoidmain(String args) Random random =new Random(6);intarraysize = 10;double sorted =new doublearraysize;System.out.println(" 排序前 :");for(intj = 0; j < arraysize; j+) sortedj = (int) (random.nextDouble() * 100);System.out.print(int) sortedj +"

30、");System.out.println();System.out.println("-");MergeSort sorter =new MergeSort();sorter.sort(sorted);System.out.println(" 排序后 :");for(intj = 0; j < sorted.length; j+) System.out.print(int) sortedj +" ");System.out.println();實驗結果：專業(yè)資料整理WORD格式9. 基數(shù)排序：專業(yè)資料整理WORD格式

31、publicclassRadixSort 專業(yè)資料整理WORD格式privateintkeyNum =-1;專業(yè)資料整理WORD格式privateVector<Vector<Double>>util;專業(yè)資料整理WORD格式publicvoiddistribute(double sorted,intnth)if(nth<=keyNum && nth>0)util=new Vector<Vector<Double>>();for( intj=0;j<10;j+)Vector <Double> temp=

32、new Vector <Double>();util.add(temp);專業(yè)資料整理WORD格式for( int int utilj=0;j<sorted.length;j+)index= getNthDigit(sortedj,nth);.get(index).add(sortedj);專業(yè)資料整理WORD格式專業(yè)資料整理WORD格式專業(yè)資料整理WORD格式publicintgetNthDigit(String nn= Ilen= nn.length();if(len>=nth)returnCharacter.doublenum,intnth)t

33、oString( int)num);getNumericValue(nn.charAt(len-nth);專業(yè)資料整理WORD格式else return0;專業(yè)資料整理WORD格式publicvoidcollect(double sorted)專業(yè)資料整理WORD格式intk=0;專業(yè)資料整理WORD格式for( intintj=0;j<10;j+) len= util.get(j).size();專業(yè)資料整理WORD格式if(len>0)專業(yè)資料整理WORD格式for( intsortedk+=i=0;i<len;i+)util.get(j).get(i);專業(yè)資料整理WORD格式util=null;專業(yè)資料整理WORD格式publicint getKeyNum( double max= Double. for ( int j=0;j<sorted. if (sortedj>max)double sorted)MIN_VALUE ;length;j+)專業(yè)資料整理WORD格式max= sortedj;returnInteger.toString( int)max).length();專業(yè)資料整理WORD格式publicvoidradixSort(do