《java排序算法大全》由会员分享，可在线阅读，更多相关《java排序算法大全（16页珍藏版）》请在金锄头文库上搜索。
1、 java排序算法大全为了便于管理，先引入个基础类：packagealgorithms;publicabstractclassSorterEextendsComparablepublicabstractvoidsort(Earray,intfrom,intlen);publicfinalvoidsort(Earray)sort(array,0,array.length); protectedfinalvoidswap(Earray,intfrom,intto) Etmp=arrayfrom;arrayfrom=arrayto;arrayto=tmp; 一 插入排序该算法在数据规模小的时候十分高
2、效，该算法每次插入第K+1到前K个有序数组中一个合适位置，K从0开始到N-1,从而完成排序：packagealgorithms;/*authoryovn*/publicclassInsertSorterEextendsComparableextendsSorterpublicvoidsort(Earray,intfrom,intlen)Etmp=null;for(inti=from+1;ifrom;j-)if(pareTo(arrayj-1)0)arrayj=arrayj-1;elsebreak;arrayj=tmp;二 冒泡排序这可能是最简单的排序算法了，算法思想是每次从数组末端开始比较相邻
3、两元素，把第i小的冒泡到数组的第i个位置。i从0一直到N-1从而完成排序。（当然也可以从数组开始端开始比较相邻两元素，把第i大的冒泡到数组的第N-i个位置。i从0一直到N-1从而完成排序。)packagealgorithms;/*authoryovn*/publicclassBubbleSorterEextendsComparableextendsSorterprivatestaticbooleanDWON=true;publicfinalvoidbubble_down(Earray,intfrom,intlen)for(inti=from;ii;j-)if(pareTo(arrayj-1)=
4、from;i-)for(intj=from;j0)swap(array,j,j+1);Overridepublicvoidsort(Earray,intfrom,intlen)if(DWON)bubble_down(array,from,len);elsebubble_up(array,from,len);三，选择排序选择排序相对于冒泡来说，它不是每次发现逆序都交换，而是在找到全局第i小的时候记下该元素位置，最后跟第i个元素交换，从而保证数组最终的有序。相对与插入排序来说，选择排序每次选出的都是全局第i小的，不会调整前i个元素了。packagealgorithms;/*authoryovn*/
5、publicclassSelectSorterEextendsComparableextendsSorter/*(non-Javadoc)*seealgorithms.Sorter#sort(E,int,int)*/Overridepublicvoidsort(Earray,intfrom,intlen)for(inti=0;ilen;i+)intsmallest=i;intj=i+from;for(;jfrom+len;j+)if(pareTo(arraysmallest)0)smallest=j;swap(array,i,smallest); 四 Shell排序Shell排序可以理解为插入
6、排序的变种，它充分利用了插入排序的两个特点：1）当数据规模小的时候非常高效2）当给定数据已经有序时的时间代价为O(N)所以，Shell排序每次把数据分成若个小块，来使用插入排序，而且之后在这若个小块排好序的情况下把它们合成大一点的小块，继续使用插入排序，不停的合并小块，知道最后成一个块，并使用插入排序。这里每次分成若干小块是通过“增量” 来控制的，开始时增量交大，接近N/2,从而使得分割出来接近N/2个小块，逐渐的减小“增量“最终到减小到1。一直较好的增量序列是2k-1,2(k-1)-1,.7,3,1,这样可使Shell排序时间复杂度达到O(N1.5)所以我在实现Shell排序的时候采用该增量
7、序列packagealgorithms;/*authoryovn*/publicclassShellSorterEextendsComparableextendsSorter/*(non-Javadoc)*Ourdeltavaluechoose2k-1,2(k-1)-1,.7,3,1.*complexityisO(n1.5)*seealgorithms.Sorter#sort(E,int,int)*/Overridepublicvoidsort(Earray,intfrom,intlen)/1.calculatethefirstdeltavalue;intvalue=1;while(value+1)*2=1;delta=(delta+1)/2-1)for(inti=0;idelta;i+)modify_insert_sort(array,from+i,len-i,delta);privatefinalvoidmodify_insert_sort(Earray,intfrom,intlen,intdelta)if(len=1)return;Etmp=null;for(inti=from+delta;ifrom;j-=delta)if(pareTo(arrayj-delta)0)arrayj=arrayj-delta;else
