java 复习003 之排序篇

2019-11-14 21:02:08

字体：大中小

来源：转载

供稿：网友

java 复习003 之排序篇

由java 复习003跳转过来的C语言实现版见some-sort-algorithms

快速排序（不稳定 O(n log n)）
packagevell.bibi.sort_algorithms;importvell.bibi.sort_algorithms.util.vell001;publicclassQuickSort{publicstaticintpartition(int[]a,intlow,inthigh){intcup;cup=a[low];//保存关键字while(high>low){while(high>low&&a[high]>=cup)high--;//由high开始找，找到小于关键字的位置a[low]=a[high];while(high>low&&a[low]<=cup)low++;//由low开始找，找到大于关键字的位置a[high]=a[low];}a[low]=cup;returnlow;}publicstaticvoidsort(int[]a,intlow,inthigh){if(high<=low)return;intmid=partition(a,low,high);//分成两个区sort(a,low,mid-1);sort(a,mid+1,high);}publicstaticvoidmain(String[]args){int[]a=vell001.getRandomList(10,100);vell001.PRintList(a);sort(a,0,a.length-1);vell001.printList(a);}}
冒泡排序（稳定 O(n2)）
packagevell.bibi.sort_algorithms;importvell.bibi.sort_algorithms.util.vell001;publicclassBubbleSort{publicstaticvoidsort(int[]a){inti,j,cup;booleanflag;for(i=a.length,flag=true;flag&&i>0;i--){flag=false;for(j=0;j<i-1;j++){if(a[j]>a[j+1]){cup=a[j];a[j]=a[j+1];a[j+1]=cup;flag=true;}}}}publicstaticvoidmain(String[]args){int[]a=vell001.getRandomList(10,100);vell001.printList(a);sort(a);vell001.printList(a);}}
希尔排序（不稳定 O(n log n)）
packagevell.bibi.sort_algorithms;importvell.bibi.sort_algorithms.util.vell001;publicclassShellSort{publicstaticvoidsort(int[]a){inti,j,d,cup;for(d=a.length/2;d>0;d=d/2){for(i=d;i<a.length;i++){cup=a[i];for(j=i-d;j>=0&&a[j]>cup;j=j-d){a[j+d]=a[j];}a[j+d]=cup;}}}publicstaticvoidmain(String[]args){int[]a=vell001.getRandomList(10,100);vell001.printList(a);sort(a);vell001.printList(a);}}
堆排序（不稳定 O(n log n)）
packagevell.bibi.sort_algorithms;importvell.bibi.sort_algorithms.util.vell001;publicclassHeapSort{publicstaticvoidheapAdjust(int[]a,intfather,intlength){intchild,cup;for(child=father*2+1,cup=a[father];child<length;father=child,child=father*2+1){if(child+1<length&&a[child+1]>a[child])child++;if(a[child]>cup){a[father]=a[child];a[child]=cup;}elsebreak;}}publicstaticvoidsort(int[]a){intcup;for(inti=a.length/2;i>=0;i--){heapAdjust(a,i,a.length);}for(inti=a.length-1;i>0;i--){cup=a[0];a[0]=a[i];a[i]=cup;heapAdjust(a,0,i);}}publicstaticvoidmain(String[]args){int[]a=vell001.getRandomList(10,100);vell001.printList(a);sort(a);vell001.printList(a);}}
归并排序（稳定 O(n log n) 需要O(n)额外空间）
packagevell.bibi.sort_algorithms;importvell.bibi.sort_algorithms.util.vell001;publicclassMergeSort{publicstaticvoidmerge(int[]a,intlow,intmid,inthigh){inti=low,j=mid,k=0;int[]cup=newint[high-low];while(i<mid&&j<high){if(a[i]<=a[j])cup[k++]=a[i++];elsecup[k++]=a[j++];}while(i<mid)cup[k++]=a[i++];while(j<high)cup[k++]=a[j++];for(k=0;k<cup.length;k++){a[low+k]=cup[k];}}publicstaticvoidsort(int[]a,intlow,inthigh){if(high-low<=1)return;intmid=(high+low)/2;sort(a,low,mid);sort(a,mid,high);merge(a,low,mid,high);}publicstaticvoidmain(String[]args){int[]a=vell001.getRandomList(10,100);vell001.printList(a);sort(a,0,a.length);vell001.printList(a);}}
vell001.java (我的小工具库)
packagevell.bibi.sort_algorithms.util;publicclassvell001{publicstaticvoidprintList(int[]a){for(inti=0;i<a.length;i++){System.out.print(a[i]+"");}System.out.println();}publicstaticint[]getRandomList(intn,intmax){int[]a=newint[n];for(inti=0;i<n;i++){a[i]=(int)(Math.random()*max);}returna;}}