常用排序算法分析与实现(Java版)

这篇排序文章从思想理解到实现，然后到整理，花了我几天的时间，现把它记录于此，希望对大家有一定的帮助，写的不好的请不要见笑，写错了的，请指出来我更正。最后如果对你有一定的帮助，请回贴支持一下哦^_^！申明：排序算法思想来自互联网，代码自己实现，仅供参考。插入排序直接插入排序、希尔排序选择排序简单选择排序、堆排序交换排序冒泡排序、快速排序归并排序基数排序排序基类Java代码1.packagesort;2.3.importjava.util.Arrays;4.importjava.util.Comparator;5.importjava.util.Random;6.7./**8.*排序接口，所有的排序算法都要继承该抽象类，并且要求数组中的9.*元素要具有比较能力，即数组元素已实现了Comparable接口10.*11.*@authorjzj12.*@date2009-12-513.*14.*@paramE15.*/16.publicabstractclassSortEextendsComparableE{17.18.publicfinalComparatorEDEFAULT_ORDER=newDefaultComparator();19.publicfinalComparatorEREVERSE_ORDER=newReverseComparator();20.21./**22.*排序算法，需实现，对数组中指定的元素进行排序23.*@paramarray待排序数组24.*@paramfrom从哪里25.*@paramend排到哪里26.*@paramc27.*/28.publicabstractvoidsort(E[]array,intfrom,intend,ComparatorEc);29.30./**31.*对数组中指定部分进行排序32.*@paramfrom从哪里33.*@paramlen排到哪里34.*@paramarray待排序数组35.*@paramc比较器36.*/37.publicvoidsort(intfrom,intlen,E[]array,ComparatorEc){38.sort(array,0,array.length-1,c);39.}40.41./**42.*对整个数组进行排序，可以使用自己的排序比较器，也可使用该类提供的两个比较器43.*@paramarray待排序数组44.*@paramc比较器45.*/46.publicfinalvoidsort(E[]array,ComparatorEc){47.sort(0,array.length,array,c);48.}49.50./**51.*对整个数组进行排序，采用默认排序比较器52.*@paramarray待排序数组53.*/54.publicfinalvoidsort(E[]array){55.sort(0,array.length,array,this.DEFAULT_ORDER);56.}57.58.//默认比较器（一般为升序，但是否真真是升序还得看E是怎样实现Comparable接口的）59.privateclassDefaultComparatorimplementsComparatorE{60.publicintcompare(Eo1,Eo2){61.returno1.compareTo(o2);62.}63.}64.65.//反序比较器，排序刚好与默认比较器相反66.privateclassReverseComparatorimplementsComparatorE{67.publicintcompare(Eo1,Eo2){68.returno2.compareTo(o1);69.}70.}71.72./**73.*交换数组中的两个元素的位置74.*@paramarray待交换的数组75.*@parami第一个元素76.*@paramj第二个元素77.*/78.protectedfinalvoidswap(E[]array,inti,intj){79.if(i!=j){//只有不是同一位置时才需交换80.Etmp=array[i];81.array[i]=array[j];82.array[j]=tmp;83.}84.}85.86./**87.*数组元素后移88.*@paramarray待移动的数组89.*@paramstartIndex从哪个开始移90.*@paramendIndex到哪个元素止91.*/92.protectedfinalvoidmove(E[]array,intstartIndex,intendIndex){93.for(inti=endIndex;i=startIndex;i--){94.array[i+1]=array[i];95.}96.}97.98./**99.*以指定的步长将数组元素后移，步长指定每个元素间的间隔100.*@paramarray待排序数组101.*@paramstartIndex从哪里开始移102.*@paramendIndex到哪个元素止103.*@paramstep步长104.*/105.protectedfinalvoidmove(E[]array,intstartIndex,intendIndex,intstep){106.for(inti=endIndex;i=startIndex;i-=step){107.array[i+step]=array[i];108.}109.}110.111.//测试方法112.@SuppressWarnings(unchecked)113.publicstaticfinalEextendsComparableEvoidtestSort(SortEsorter,E[]array){114.115.if(array==null){116.array=randomArray();117.}118.//为了第二次排序，需拷贝一份119.E[]tmpArr=(E[])newComparable[array.length];120.System.arraycopy(array,0,tmpArr,0,array.length);121.122.System.out.println(源-+Arrays.toString(tmpArr));123.124.sorter.sort(array,sorter.REVERSE_ORDER);125.System.out.println(降-+Arrays.toString(array));126.127.sorter.sort(tmpArr,sorter.DEFAULT_ORDER);128.System.out.println(升-+Arrays.toString(tmpArr));129.}130.131.//生成随机数组132.@SuppressWarnings(unchecked)133.privatestaticEextendsComparableEE[]randomArray(){134.Randomr=newRandom(System.currentTimeMillis());135.Integer[]a=newInteger[r.nextInt(30)];136.for(inti=0;ia.length;i++){137.a[i]=newInteger(r.nextInt(100));138.}139.return(E[])a;140.}141.}插入排序直接插入排序一般直接插入排序的时间复杂度为O(n^2)，但是当数列基本有序时，如果按照有数列顺序排时，时间复杂度将改善到O(n)，另外，因直接插入排序算法简单，如果待排序列规模不很大时效率也较高。在已经排好序的序列中查找待插入的元素的插入位置，并将待插入元素插入到有序列表中的过程。将数组分成两部分，初始化时，前部分数组为只有第一个元素，用来存储已排序元素，我们这里叫arr1；后部分数组的元素为除第一个元素的所有元素，为待排序或待插入元素，我们这里叫arr2。排序时使用二层循环：第一层对arr2进行循环，每次取后部分数组（待排序数组）里的第一个元素（我们称为待排序元素或称待插入元素）e1，然后在第二层循环中对arr1（已排好序的数组）从第一个元素往后进行循环，查到第一个大于待插入元素（如果是升序排列）或第一个小于待插入元素（如果是降序排列）e2，然后对arr1从e2元素开始往后的所有元素向后移，最后把e1插入到原来e2所在的位置。这样反复地对arr2进行循环，直到arr2中所有的待插入的元素都插入到arr1中。Java代码1.packagesort;2.3.importjava.util.Comparator;4.5./**6.*直接插入排序算法7.*@authorjzj8.*@date2009-12-59.*10.*@paramE11.*/12.publicclassInsertSortEextendsComparableEextendsSortE{13.14./**15.*排序算法的实现，对数组中指定的元素进行排序16.*@paramarray待排序的数组17.*@paramfrom从哪里开始排序18.*@paramend排到哪里19.*@paramc比较器20.*/21.publicvoidsort(E[]array,intfrom,intend,ComparatorEc){22.23./*24.*第一层循环：对待插入（排序）的元素进行循环25.*从待排序数组断的第二个元素开始循环，到最后一个元素（包括）止26.*/27.for(inti=from+1;i=end;i++){28./*29.*第二层循环：对有序数组进行循环，且从有序数组最第一个元素开始向后循环30.*找到第一个大于待插入的元素31.*有序数组初始元素只有一个，且为源数组的第一个元素，一个元素数组总是有序的32.*/33.for(intj=0;ji;j++){34.EinsertedElem=array[i];//待插入到有序数组的元素35.//从有序数组中最一个元素开始查找第一个大于待插入的元素36.if(c.compare(array[j],insertedElem)0){37.//找到插入点后，从插入点开始向后所有元素后移一位38.move(array,j,i-1);39.//将待排序元素插入到有序数组中40.array[j]=insertedElem;41.break;42.}43.}44.}45.46.//=======以下是java.util.Arrays的插入排序算法的实现47./*48.*该算法看起来比较简洁一j点，有点像冒泡算法。49.*将数组逻辑上分成前后两个集合，前面的集合是已经排序好序的元素，而后面集合为待排序的50.*集合，每次内层循从后面集合中拿出一个元素，通过冒泡的形式，从前面集合最后一个元素开51.*始往前比较，如果发现前面元素大于后面元素，则交换，否则循环退出52.*53.*总感觉这种算术有点怪怪，既然是插入排序，应该是先找到插入点，而后再将待排序的元素插54.*入到的插入点上，那么其他元素就必然向后移，感觉算法与排序名称不匹，但返过来与上面实55.*现比，其实是一样的，只是上面先找插入点，待找到后一次性将大的元素向后移，而该算法却56.*是走一步看一步，一步一步将待排序元素往前移57.*/58./*59.for(inti=from;i=end;i++){60.for(intj=i;jfrom&&c.compare(array[j-1],array[j])0;j--){61.swap(array,j,j-1);62.}63.}64.*/65.}66.67./**68.*测试69.*@paramargs70.*/71.publicst