java排序算法大全.doc

java排序算法大全为了便于管理,先引入个基础类:packagealgorithms;publicabstractclassSorter<parable<E>>{publicabstractvoidsort(E[]array,intfrom,intlen);publicfinalvoidsort(E[]array){sort(array,0,);}protectedfinalvoidswap(E[]array,intfrom,intto){Etmp=array[from];array[from]=array[to];array[to]=tmp;}}一插入排序该算法在数据规模小的时候十分高效,该算法每次插入第K+1到前K个有序数组中一个合适位置,K从0开始到N-1,从而完成排序:packagealgorithms;/******@authoryovn*/lassInsertSorter<parable<E>>extendsSorter<E>{/*(non-Javadoc)****@#sort(E[],int,int)*/publicvoidsort(E[]array,intfrom,intlen){Etmp=null;for(inti=from+1;i<from+len;i++){tmp=array[i];intj=i;for(;j>from;j--){if(pareTo(array[j-1])<0){array[j]=array[j-1];}elsebreak;}array[j]=tmp;}}}二冒泡排序这可能是最简单的排序算法了,算法思想是每次从数组末端开始比较相邻两元素,把第i小的冒泡到数组的第i个位置。i从0一直到N-1从而完成排序。(当然也可以从数组开始端开始比较相邻两元素,把第i大的冒泡到数组的第N-i个位置。i从0一直到N-1从而完成排序。)packagealgorithms;/******@authoryovn**/lassBubbleSorter<parable<E>>extendsSorter<E>{privatestaticbooleanDWON=true;publicfinalvoidbubble_down(E[]array,intfrom,intlen){for(inti=from;i<from+len;i++){for(intj=from+len-1;j>i;j--){if(array[j].compareTo(array[j-1])<0){swap(array,j-1,j);}}}}publicfinalvoidbubble_up(E[]array,intfrom,intlen){for(inti=from+len-1;i>=from;i--){for(intj=from;j<i;j++){if(array[j].compareTo(array[j+1])>0){swap(array,j,j+1);}}}}***@Overridepublicvoidsort(E[]array,intfrom,intlen){if(DWON){bubble_down(array,from,len);}else{bubble_up(array,from,len);}}}三,选择排序选择排序相对于冒泡来说,它不是每次发现逆序都交换,而是在找到全局第i小的时候记下该元素位置,最后跟第i个元素交换,从而保证数组最终的有序。相对与插入排序来说,选择排序每次选出的都是全局第i小的,不会调整前i个元素了。packagealgorithms;/******@authoryovn**/lassSelectSorter<parable<E>>extendsSorter<E>{/*(non-Javadoc)****@#sort(E[],int,int)*/***@Overridepublicvoidsort(E[]array,intfrom,intlen){for(inti=0;i<len;i++){intsmallest=i;intj=i+from;for(;j<from+len;j++){if(array[j].compareTo(array[smallest])<0){smallest=j;}}swap(array,i,smallest);}}}四Shell排序Shell排序可以理解为插入排序的变种,它充分利用了插入排序的两个特点:1)当数据规模小的时候非常高效2)当给定数据已经有序时的时间代价为O(N)所以,Shell排序每次把数据分成若个小块,来使用插入排序,而且之后在这若个小块排好序的情况下把它们合成大一点的小块,继续使用插入排序,不停的合并小块,知道最后成一个块,