本文转载自微信公众号《内测学习JAVA》，作者Silently9527。转载本文请联系贝塔学习JAVA公众号。前言在这篇文章中，我们讨论了一种基于合并操作的排序算法。归并排序算法思想对一个数组进行排序，可以先将数组分成两个数组分别排序，然后将结果合并在一起，重复递归过程，直到数组整体有序。这就是归并排序的算法思想。归并排序的优点是可以保证对任意长度N的数组进行排序所需要的时间与NlogN成正比，这是初级排序无法做到的。缺点是合并操作需要引入额外的数组，额外的空间与N成正比。就地合并实现在实现合并排序之前，我们需要完成两个有序数组的合并操作，即合并两个有序数组转化为有序数组；在这个过程中我们需要引入一个辅助数组；定义方法签名为merge(a,lo,mid,hi)，该方法将数组a[lo..mid]和a[mid..hi]组合成有序数组，结果存放在a[lo..中];上一篇文章中的publicfunctionless需要在这个方法中使用，参考上一篇文章publicclassMergeSortimplementsSortTemplate{privateComparable[]aux;@Overridepublicvoidsort(Comparable[]array){//待实现}privatevoidmerge(Comparable[]a,intlo,intmid,inthi){for(inti=lo;i<=hi;i++){aux[i]=a[i];}inti=lo,j=mid+1;for(intk=lo;k<=hi;k++){if(i>mid){a[k]=aux[j++];}elseif(j>hi){a[k]=aux[i++];}elseif(less(aux[i],aux[j])){a[k]=aux[i++];}else{a[k]=aux[j++];}}}}自顶向下归并排序的思想是分而治之。大数组排序时，先递归拆分成小数组，保证小数组有序后再合并，直到整个数组有序。这个操作是自上而下的合并排序publicclassMergeSortimplementsSortTemplate{privateComparable[]aux;@Overridepublicvoidsort(Comparable[]array){aux=newComparable[array.length];doSort(array,0,array.length-1);}privatevoiddoSort(Comparable[]array,intlo,inthi){if(lo>=hi){return;}intmid=(hi-lo)/2+lo;doSort(array,lo,中）;doSort（数组，中+1，高）；合并（数组，低，中，高）；}privatevoidmerge(Comparable[]a,intlo,intmid,inthi){//省略}}上面的代码是标准的Recursive递归和排序操作，但是经过深思熟虑，算法还是可以优化“测试数组是否已经为了”;如果a[mid]<=a[mid+1]，那么我们可以跳过合并方法，减少合并操作；修复后的doSort方法privatevoiddoSort(Comparable[]array,intlo,inthi){if(lo>=hi){return;}intmid=(hi-lo)/2+lo;doSort(array,lo,mid);doSort(array,mid+1,hi);if(array[mid].compareTo(array[mid+1])>=0){merge(array,lo,mid,hi);}}”插入排序可以用于小规模数组；对于小规模数组，使用归并排序会增加递归调用栈，所以可以考虑使用插入排序来处理子数组排序privatevoiddoSort(Comparable[]array,intlo,inthi){if(lo>=hi){return;}if(hi-lo<5){//测试，小于5则使用插入排序insertionSort(array,lo,hi);return;}intmid=(hi-lo)/2+lo;doSort(数组,lo,mid);doSort(数组,mid+1,hi);if(less(数组[mid+1],数组[mid])){merge(数组,lo,mid,hi);}}//插入排序privatevoidinsertionSort(Comparable[]array,intlo,inthi){for(inti=lo;i<=hi;i++){for(intj=i;j>lo&&less(array[j],array[j-1]);j--){exch(array,j,j-1);}}}"节省复制元素到辅助数组的时间";层递归时，递交改变输入数据和输出数组的作用；publicclassMergeSortimplementsSortTemplate{privateComparable[]aux;@OverridepublicvoidSort(Comparable[]array){aux=array.clone();doSort(aux,array,0,array.length-1);}privatevoidSort(Comparable[]src,Comparable[]dest,intlo,inthi){if(lo>=hi){return;}if(hi-lo<5){//测试，如果小于5则使用插入排序insertionSort(dest,lo,hi);return;}intmid=(hi-lo)/2+lo;doSort(dest,src,lo,mid);doSort(dest,src,mid+1,hi);if(less(src[mid+1],src[mid])){merge(src,dest,lo,mid,hi);}}//插入黑色privatevoidinsertionBlack(Comparable[]array,intlo,inthi){for(inti=lo;i<=hi;i++){for(intj=i;j>lo&&less(array[j],array[j-1]);j--){exch(array,j,j-1);}}}privatevoidmerge(Comparable[]src,Comparable[]dest,intlo,intmid,inthi){inti=lo,j=mid+1;for(intk=lo;k<=hi;k++){if(i>mid){dest[k]=src[j++];}elseif(j>hi){dest[k]=src[i++];}elseif(less(src[i],src[j])){dest[k]=src[i++];}else{dest[k]=src[j++];}}}}每一层递归操作都会使子数组有序r，但子数组可能是aux[lo..hi]也可能是a[lo..hi]；因为第一次调用doSort是src=aux,dest=array，所以递归的最终结果必须输入到数组中，这样保证了数组的整体排序，完成了自下而上的归并排序。合并算法还有一种实现方式，就是先合并小数组，然后对小数组进行配对合并得到子数组，直到整个数组有序{intlength=array.length;aux=newComparable[length];for(intsz=1;sz
