先推荐一篇关于排序算法的文章：/guogangj/archive//11/13/100876.html
本文思路部分来源于上篇文章，但测得的结果似乎不大相同，不知是因为java的缘故还是因为我算法的缘故，欢迎拍砖。
复习排序，顺便比下各种算法的速度，榜单如下：
1、冒泡排序
2、简单选择排序
3、直接插入排序
4、折半插入排序
5、希尔排序
6、堆排序
7、归并排序
8、快速排序
当然这是慢速排行，哈哈~~
直接上图：单位毫秒
由于"希尔排序","堆排序","归并排序","快速排序"太快，以至于在上图几乎是条直线，故有了下面转为他们准备的加强版
补上代码：
Java代码 importjava.util.ArrayList; importjava.util.Arrays; importjava.util.List; /** *插入排序:直接插入排序、折半插入排序和系尔排序 *交换排序:冒泡排序和快速排序 *选择排序:简单选择排序和堆排序 *归并排序:归并排序 * *基本思想 *插入排序:将第N个记录插入到前面(N-1)个有序的记录当中。 *交换排序:按照某种顺序比较两个记录的关键字大小，然后根据需要交换两个记录的位置。 *选择排序:根据某种方法选择一个关键字最大的记录或者关键字最小的记录，放到适当的位置。 * *排序方法比较 *排序方法平均时间最坏时间辅助存储 *直接插入排序O(N2)O(N2)O(1) *起泡排序O(N2)O(N2)O(1) *快速排序O(Nlog2N)O(N2)O(Nlog2N) *简单选择排序O(N2)O(N2)O(1) *堆排序O(Nlog2N)O(Nlog2N)O(1) *归并排序O(Nlog2N)O(Nlog2N)O(n) *基数排序O(d(n+radix))O(d(n+radix))O(radix) * * * *@authorAdministrator * */publicclassSortTest{ publicstaticvoidmain(String[]args)throwsException{ //测试排序是否正确 //String[]testErr=newString[]{"冒泡排序","简单选择排序","直接插入排序","折半插入排序","系尔排序","堆排序","归并排序","快速排序"}; //newSortTest().testErr(testErr); //排序1（全部） String[]strs=newString[]{"冒泡排序","简单选择排序","直接插入排序","折半插入排序","希尔排序","堆排序","归并排序","快速排序"}; newSortTest().test(strs,10000,50000,5000); //排序2（加强） String[]strs2=newString[]{"希尔排序","堆排序","归并排序","快速排序"}; newSortTest().test(strs2,100000,1900000,100000); } privatevoidtestErr(String[]strings)throwsException{ //System.out.println(Arrays.toString(old)); System.out.println(Arrays.toString(strings)); Number[]old=getRundom(50); Integer[]oo={1,2,3,3,2,21,5,6,7,78,5,65,8,7,6,6,6,6,6,9,56544,354,32,4,456,8,89,-9,0,3,243,-321,321,-3,-2,21}; old=oo; for(Strings:strings){ Number[]testNum=Arrays.copyOf(old,old.length); longbegin=System.currentTimeMillis(); SortTest.class.getMethod(s,Number[].class).invoke(this,(Object)testNum); longend=System.currentTimeMillis(); System.out.println(s+":"+(end-begin)+"\t"); System.out.println(Arrays.toString(testNum)); } System.out.println(); } privatevoidtest(String[]strings,longbegin,longend,longstep)throwsException{ System.out.print("数量\t"); for(Stringstr:strings){ System.out.print(str+"\t"); } System.out.println(); for(longi=begin;i<end;i=i+step){ System.out.print(i+"个\t"); Number[]old=getRundom(i); for(Strings:strings){ Number[]testNum=Arrays.copyOf(old,old.length); longbeginTime=System.currentTimeMillis(); SortTest.class.getMethod(s,Number[].class).invoke(this,(Object)testNum); longendTime=System.currentTimeMillis(); System.out.print((endTime-beginTime)+"\t"); //System.out.println(Arrays.toString(testNum)); } System.out.println(); } } privatestaticInteger[]getRundom(longnum){ List<Integer>list=newArrayList<Integer>(); for(longi=0;i<num;i++){ intk; if(Math.random()>0.5){ k=(int)(Math.random()*Integer.MAX_VALUE); }else{ k=(int)(Math.random()*Integer.MIN_VALUE); } list.add(k); } returnlist.toArray(newInteger[list.size()]); }/** *插入排序————直接插入排序 *@paramdata */publicstaticvoid直接插入排序(Number[]data) { Numbertmp=null; for(inti=1;i<data.length;i++){ tmp=data[i]; intj=i-1; while(j>=0&&tmp.doubleValue()<data[j].doubleValue()){ data[j+1]=data[j]; j--; } data[j+1]=tmp; } } /** *插入排序————折半插入排序 *@paramdata */publicstaticvoid折半插入排序(Number[]data) { Numbertmp=null; for(inti=1;i<data.length;i++){ tmp=data[i]; intsmallpoint=0; intbigpoint=i-1; while(bigpoint>=smallpoint){ intmid=(smallpoint+bigpoint)/2; if(tmp.doubleValue()>data[mid].doubleValue()){ smallpoint=mid+1; }else{ bigpoint=mid-1; } } for(intj=i;j>smallpoint;j--){ data[j]=data[j-1]; } data[bigpoint+1]=tmp; } } /** *插入排序————希尔排序 *@paramdata */publicstaticvoid希尔排序(Number[]data) { intspan=data.length/7; if(span==0)span=1; while(span>=1){ for(inti=0;i<span;i++){ for(intj=i;j<data.length;j=j+span){ //组内直接插入排序 intp=j-span; Numbertemp=data[j]; while(p>=0&&data[p].doubleValue()>temp.doubleValue()){ data[p+span]=data[p]; p-=span; } data[p+span]=temp; } } span=span/2; } } /** *交换排序————冒泡排序 * *@paramdata */publicstaticvoid冒泡排序(Number[]data) { for(inti=0;i<data.length;i++){ //将相邻两个数进行比较，较大的数往后冒泡 for(intj=0;j<data.length-i-1;j++){ if(data[j].doubleValue()>data[j+1].doubleValue()){ //交换相邻两个数 swap(data,j,j+1); } } } } /** *交换排序————快速排序 *@paramdata */publicstaticvoid快速排序(Number[]data) { QuickSort(data,0,data.length-1); } privatestaticvoidQuickSort(Number[]data,intbegin,intend){ //System.out.println(begin+":"+end); if(begin<end){ //取中点 intmid=(begin+end)/2; if(data[end].doubleValue()<data[begin].doubleValue()){ swap(data,end,begin); } if(data[end].doubleValue()<data[mid].doubleValue()){ swap(data,end,mid); } if(data[mid].doubleValue()<data[begin].doubleValue()){ swap(data,mid,begin); } swap(data,mid,begin); //System.out.println(Arrays.toString(Arrays.copyOfRange(data,begin,end))); intmin=begin+1; intbig=end; while(true){ while(min<big&&data[min].doubleValue()<data[begin].doubleValue()){min++;} while(min<big&&data[big].doubleValue()>=data[begin].doubleValue()){big--;} if(min>=big){ break; } swap(data,min,big); } if(data[begin].doubleValue()>data[min].doubleValue()){ swap(data,begin,min); } if(min>1) QuickSort(data,begin,min-1); //if(min<end) QuickSort(data,min,end); } } /** *选择排序————简单选择排序 *@paramdata */publicstaticvoid简单选择排序(Number[]data) { for(inti=0;i<data.length-1;i++){ intsmallPoint=i; for(intj=i+1;j<data.length;j++){ if(data[smallPoint].doubleValue()>data[j].doubleValue()){ smallPoint=j; } } swap(data,i,smallPoint); } } /** *选择排序————堆排序 *@paramdata */publicstaticvoid堆排序(Number[]data) { intn=data.length; for(inti=n/2;i>=0;i--){ keepHeap(data,n,i); } while(n>0){ swap(data,0,n-1); keepHeap(data,--n,0); } } privatestaticvoidkeepHeap(Number[]a,intn,inti){ Numberx=a[i]; intj=2*i+1; while(j<=n-1){ if(j<n-1&&a[j].doubleValue()<a[j+1].doubleValue()) ++j; if(a[j].doubleValue()>x.doubleValue()){ a[i]=a[j]; i=j; j=2*i; }else{ break; } } a[i]=x; }/** *归并排序法————归并排序 *@paramdata */publicstaticvoid归并排序(Number[]data) { Number[]result=merge_sort(data,0,data.length-1); for(inti=0;i<result.length;i++){ data[i]=result[i]; } } privatestaticNumber[]merge_sort(Number[]array,intstart,intend){ Number[]result=newNumber[end-start+1]; if(start<end){ intmid=(start+end)/2; Number[]left=merge_sort(array,start,mid); Number[]right=merge_sort(array,mid+1,end); result=merge(left,right); }elseif(start==end){ result[0]=array[start]; returnresult; } returnresult; } privatestaticNumber[]merge(Number[]left,Number[]right){ Number[]result=newNumber[left.length+right.length]; inti=0; intj=0; intk=0; while(i<left.length&&j<right.length){ if(left[i].doubleValue()<right[j].doubleValue()){ result[k++]=left[i++]; }else{ result[k++]=right[j++]; } } while(i<left.length){ result[k++]=left[i++]; } while(j<right.length){ result[k++]=right[j++]; } returnresult; } /** *交换数组中指定的两元素的位置 *@paramdata *@paramx *@paramy */privatestaticvoidswap(Number[]data,intx,inty){ Numbertemp=data[x]; data[x]=data[y]; data[y]=temp; } }
排序算法java版 速度排行：冒泡排序 简单选择排序 直接插入排序 折半插入排序 希尔排序 堆排序 归并排序 快速排序...
