数据结构课程设计之java排序

《数据结构课程设计》专业:计算机科学与技术

姓名：周兵学号:030940122、需求分析一、设计代码：1.直接插入排序：publicclassInsertSort{publicstatic<TextendsComparable<?superT>>voidinsertSort(T[]insertSort(T[]array){for(inti=1;i<=array.length-1;i++){intj=i;while(j>=1&&array[j].compareTo(array[j-1])<0){Ttemp=array[j];array[j]=array[j-1];array[j-1]=temp;j--;}}}publicstaticvoidmain(String[]args){Integer]]testArray={23,25,12,42,35,33,43,57};Systemout.println("排序前:");for(Integeritem:testArray){Systeout.print(item);Systeout.print('');}Systemout.println();Systemout.println(" ");InsertSortinsertSort(testArray);Systemout.println("排序后:");for(Integeritem:testArray){Systeout.print(item);Systeout.print('');}}}实验结果：2.折半插入排序：publicclassBlnsertSort{publicstaticvoidbInsertSort(int[]temp){intlength=temp.length;for(inti=1;i<length;i++){inttempVal=temp[i];intlow=0;inthigh=i-1;while(low<=high){intmiddle=(low+high)/2;if(tempVal<temp[middle])high=middle-1;elselow=middle+1;}for(intj=i;j>high+1;j--)temp[j]=temp[j-1];temp[high+1]=tempVal;}}publicstaticvoidmain(String[]args){int[]a={5,1,76,2,4,84,36,22,62,90};blnsertSort(a);System.out.println("排序后:")；for(inti=0;i<a.length;i++)System.out.print(a[i]+"");}}实验结果：errTiinated>BinsertSort[JavaApplication]E:VAVA'i.jre6\bin\javaw.exe(May19,201112:46:46AMjX浪昼瘟虔I更I苗国rv排序前：5176248436226290排序后：12452236627684903.希尔排序:publicclassInsertionSort{publicvoidshellInertionSort(doUble[]sorted,intinc){intsortedLen=sorted.length;for(intj=inc+1;j<sortedLen;j++){if(sorted[j]<sorted[j-inc]){sorted[0]=sorted[j//先保存一下后面的那个intinsertPos=j;for(intk=j-inc;k>=0;k-=inc){if(sorted[k]>sorted[0]){sorted[k+inc]=sorted[k];if(k-inc<=0){insertPos=k;}else{insertPos=k+inc;break;}I}sorted[insertPos]=sorted[0];}}}pUblicvoidshellInsertionSort(doUble[]sorted){int[]incs={7,5,3,1};intnum=incs.length;intinc=0;for(intj=0;j<num;j++){inc=incs[j];shellInertionSort(sorted,inc);publicstaticvoidmain(String[]args){Randomrandom=newRandom(6);intarraysize=21;double[]sorted=newdouble[arraysize];Systemout.print("BeforeSort:");for(intj=1;j<arraysize;j++){sorted[j]=int)(random.nextDouble()*100);Systeout.print((int)sorted[j]+"");}Systemout.println();InsertionSortsorternewInsertionSort();sorter.shellInsertionSort(sorted);Systemout.print("AfterSort:");for(intj=1;j<sorted.length;j++){Systemout.print((int)sorted[j]+"");}Systemout.println();}}实验结果：%FrobiAms Tasks曰Consolt!£3\Servers X领{Itermiriated)InEertioriSort[JavaApplication]E:\JAVAAjre6'lbin'l.javaw.exe(May19】2011非序前门35777113367.54891非序后1133.545767737789冒泡排序:publicclassBubbluSort{publicstaticvoidsortiere(int[]x){booleanunsortiert=true;inttemp;while(unsortiert){unsortiert=false;for(inti=0;i<x.length-1;i++)if(x[i]>x[i+1]){temp=x[i];x[i]=x[i+1];x[i+1]=temp;unsortiert=true;}publicstaticvoidmain(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(liste[i]+"");System.out.println();System.out.println(" System.out.println("排序后：”);sortiere(liste);for(inti=0;i<liste.length;i++)System.out.print(liste[i]+"");实验结果:FrublemeTasks§Console於Servers XFrubleme<+HrmirLathEuhbluSort[JavaApplication]E:'yJAVA'1!.jre6'i.binAjavaw.exe(May19,2011排序前：0946285173排序后：0123456789快速排序：publicclassExchangeSort{publicvoidQuickExchangeSortBackTrack(double[]sorted,intlow,inthigh){if(low<high){intpivot=findPivot(sorted,low,high);QuickExchangeSortBackTrack(sorted,low,pivot-1);QuickExchangeSortBackTrack(sorted,pivot+1,high);}}publicintfindPivot(double[]sorted,intlow,inthigh){sorted[0]=sorted[low];

while(low<high){while(low<high&&sorted[high]>=sorted[0])--high;sorted[low]=sorted[high];while(low<high&&sorted[low]<=sorted[0])++low;sorted[high]=sorted[low];}sorted[low]=sorted[0];returnlow;publicstaticvoidmain(String[]args){

Randomrandom=newRandom(6);

intarraysize=10;

double[]sorted=newdouble[arraysize];

System.out.println("排序前:");

for(intj=1;j<arraysize;j++){

sorted[j]=(int)(random.nextDouble()*100);

System.out.print((int)sorted[j]+"");

}

System.out.println();

System.out.println(" ");实验结果实验结果:ExchangeSortsorter=newExchangeSort();sorter.QuickExchangeSortBackTrack(sorted,1,arraysize-1);System.out.println("排序后:");for(intj=1;j<sorted.length;j++){System.out.print((int)sorted[j]+"");}System.out.println();实验结果实验结果:Frobleas^,terminated)'ExchangeSort.[JavaApplication.]E：\JAVA\jre6\bin\javaw.exe(May19,2011排序前:73577711336754S91排序后:111335457677377S9直接选择排序:publicclassSelectionSort{

publicvoidstraitSelectionSort(double[]sorted){intsortedLen=sorted.length;for(intj=1;j<sortedLen;j++){intjMin=getMinIndex(sorted,j);exchange(sorted,j,jMin);}}publicvoidexchange(double[]sorted,inti,intj){intsortedLen=sorted.length;if(i<sortedLen&&j<sortedLen&&i<j&&i>=0&&j>=0){doubletemp=sorted[i];sorted[i]=sorted[j];sorted[j]=temp;}}publicintgetMinIndex(double[]sorted,inti){intsortedLen=sorted.length;intminJ=1;doublemin=Double.MAX_VALUE;for(intj=i;j<sortedLen;j++){if(sorted[j]<min){min=sorted[j];minJ=j;}}returnminJ;}publicstaticvoidmain(String[]args){Randomrandom=newRandom(6);intarraysize=9;double[]sorted=newdouble[arraysize];Systemout.println("排序前:");for(intj=1;j<arraysize;j++){sorted[j]=int)(random.nextDouble()*100);Systeout.print((int)sorted[j]+"");}Systemout.println();Systemout.println(" ");SelectionSortsorternewSelectionSort();sorter.straitSelectionSort(sorted);Systemout.println("排序后:");for(intj=1;j<sorted.length;j++){Systeout.print((int)sorted[j]+}Systemout.println();}}实验结果:度IFrublemeTasks目Console汶 Servers X峰(l^,terminated^SelectionSort[JavaApplication]E：\JAVA\jre6\bin\javaw.exe(May19?2011!排序前：73577711336754S9排序后：11335457677377S9堆排序：publicclassSelectionSort{publicvoidheapAdjust(double[]sorted,intstart,intend){if(start<end){doubletemp=sorted[start];for(intj=2*start;j<end;j*=2){if(j+1<end&&sorted[j]-sorted[j+1]>10e-6){++j;}if(temp<=sorted[j]){break;}sorted[start]=sorted[j];start=j;}sorted[start]=temp;}}publicvoidexchange(double[]sorted,inti,intj){intsortedLen=sorted.length;if(i<sortedLen&&j<sortedLen&&i<j&&i>=0&&j>=0){doubletemp=sorted[i];sorted[i]=sorted[j];sorted[j]=temp;}}publicvoidheapSelectionSort(double[]sorted){intsortedLen=sorted.length;for(inti=sortedLen/2;i>0;i--){heapAdjust(sorted,i,sortedLen);}for(inti=sortedLen;i>1;--i){exchange(sorted,1,i);heapAdjust(sorted,1,i-1);}}publicstaticvoidmain(String[]args){Randomrandom=newRandom(6);intarraysize=10;double[]sorted=newdouble[arraysize];Systemout.println("排序前:");for(intj=1;j<arraysize;j++){sorted[j]=int)(random.nextDouble()*100);Systeout.print((int)sorted[j]+"");}Systemout.println();Systemout.println(" ");SelectionSortsorternewSelectionSort();sorter.heapSelectionSort(sorted);Systemout.println("排序后:");for(intj=1;j<sorted.length;j++){Systeout.print((int)sorted[j]+"");}Systemout.println();}}实验结果：8.归并排序：publicclassMergeSort{privatedouble[]bridge;//辅助数组publicvoidsort(doUble[]obj){if(obj==null){thrownewNullPointerException("Theparamcannotbenull!");}bridge=newdouble[obj.length];//初始化中间数组mergeSort(obj,0,objlength-1);//归并排序bridge=null;}privatevoidmergeSort(double[]obj,intleft,intright){if(left<right){intcenter=(left+right)/2;mergeSort(obj,left,center);mergeSort(obj,center+1,right);merge(obj,left,center,right);}}privatevoidmerge(double[]obj,intleft,intcenter,intright){intmid=center+1;intthird=left;inttmp=left;while(left<=center&&mid<=right){if(obj[left]-obj[mid]<=10e-6){bridge[third++]=obj[left++];else{bridge[third++]=obj[mid++];}}while(mid<=right){bridge[third++]=obj[mid++];}while(left<=center){bridge[third++]=obj[left++];}//将中间数组的内容拷贝回原数组copy(obj,tmp,right);}privatevoidcopy(double[]obj,intleft,intright){while(left<=right){obj[left]bridge[left];left++;}}publicstaticvoidmain(String[]args){Randomrandom=newRandom(6);intarraysize=10;double]]sorted=newdouble[arraysize];Systemout.println("排序前:");for(intj=0;j<arraysize;j++){sorted[j]=int)(random.nextDouble()*100);Systeout.print((int)sorted[j]+"");}Systemout.println();Systemout.println(" ");MergeSortsorter=newMergeSort();sorter.sort(sorted);Systemout.println("排序后:");for(intj=0;j<sorted.length;j++){Systeout.print((int)sorted[j]+"");}Systemout.println();}}实验结果：I•'FrobleasTasks目Console於泉Servers 暮认^terminated^MergeSort[JavaApplication]E：\JAVA\jre6\.bin\javaw.exe(May19,20117:5排序前：73577711336754S9193排序后：111335457677377S9939.基数排序：publicclassRadixSort{privateintkeyNum=-1;privateVector<Vector<Double>>util;publicvoiddistribute(doUble[]sorted,intnth){if(nth<=keyNum&&nth>0){util=newVector<Vector<Double>>();for(intj=0;j<10;j++){Vector<Double>temnewVector<Double>();util.add(temp);}for(intj=0;j<sorted.length;j++){intindex=getNthDigit(sorted[j],nth);util.get(index).add(sorted[j]);}}}pUblicintgetNthDigit(doUblenum,intnth){Stringnn=Integert.oString((int)num);intlen=nn.length();if(len>=nth){returnCharacter.getNumericValue(nn.charAt(len-nth));else{return0;}}publicvoidcollect(double[]sorted){intk=0;for(intj=0;j<10;j++){intlen=util.get(j).size();if(len>0){for(inti=0;i<len;i++){sorted[k+util.get(j).get(i);}}}util=null;}publicintgetKeyNum(double[]sorted){doublemax=Double.MIN_VALUE;for(int