深入探究TimSort对归并排序算法的优化及Java实现
简介
MergeSort对已经反向排好序的输入时复杂度为O(n^2),而timsort就是针对这种情况,对MergeSort进行优化而产生的,平均复杂度为n*O(logn),最好的情况为O(n),最坏情况n*O(logn)。并且TimSort是一种稳定性排序。思想是先对待排序列进行分区,然后再对分区进行合并,看起来和MergeSort步骤一样,但是其中有一些针对反向和大规模数据的优化处理。
归并排序的优化思想
归并排序有以下几点优化方法:
和快速排序一样,对于小数组可以使用插入排序或者选择排序,避免递归调用。
在merge()调用之前,可以判断一下a[mid]是否小于等于a[mid+1]。如果是的话那么就不用归并了,数组已经是有序的。原因很简单,既然两个子数组已经有序了,那么a[mid]是第一个子数组的最大值,a[mid+1]是第二个子数组的最小值。当a[mid]<=a[mid+1]时,数组整体有序。
为了节省将元素复制到辅助数组作用的时间,可以在递归调用的每个层次交换原始数组与辅助数组的角色。
在merge()方法中的归并过程需要判断i和j是否已经越界,即某半边已经用尽。可以用另一种方式,去掉检测是否某半边已经用尽的代码。具体步骤是将数组a[]的后半部分以降序的方式复制到aux[],然后从两端归并。对于数组{1,2,3}和{2,3,5},第一个子数组照常复制,第二个则从后往前复制,最终aux[]中的元素为{1,2,3,5,3,2}。这种方法的缺点是使得归并排序变为不稳定排序。代码实现如下:
voidmerge(int[]a,intlo,intmid,inthi,int[]aux){ for(intk=lo;k<=mid;k++){ aux[k]=a[k]; } for(intk=mid+1;k<=hi;k++){ aux[k]=a[hi-k+mid+1]; } inti=lo,j=hi;//从两端往中间 for(intk=lo;k<=hi;k++) if(aux[i]<=aux[j])a[k]=aux[i++]; elsea[k]=aux[j--]; }
TimSort的步骤
分区
分区的思想是扫描一次数组,把连续正序列(如果是升序排序,那么正序列就是升序序列),或者【严格】(保证排序算法的稳定性)的反序列做为一个分区(run),如果是反序列,把分区里的元素反转一下。例如
1,2,3,6,4,5,8,6,4划分分区结果为
[1,2,3,6],[4,5,8],[6,4]
然后反转反序列
[1,2,3,6],[4,5,8],[4,6]
合并
考虑一个极端的例子,比如分区的长度分别为10000,10,1000,10,10,我们当然希望是先让10个10合并成20,20和1000合并成1020如此下去,如果从从左往右顺序合并的话,每次都用到10000这个数组和去小的数组合并,代价太大了。所以我们可以用一个策略来优化合并的顺序。
实例
以java中的ComparableTimSort.sort()为例子,用了一个runstack来确定是否应该合并,
if(nRemaining<MIN_MERGE){ intinitRunLen=countRunAndMakeAscending(a,lo,hi); binarySort(a,lo,hi,lo+initRunLen); return; }
小于MIN_MERGE(32)的排序,分区后直接用二分插入排序
intminRun=minRunLength(nRemaining); do{ //找出下一个分区的起始位置,同时也对反向序列做了翻转处理 intrunLen=countRunAndMakeAscending(a,lo,hi); //保证runstack中的run的都大于minRun,如果当前分区太小,就从后面取出元素补足 if(runLen<minRun){ intforce=nRemaining<=minRun?nRemaining:minRun; binarySort(a,lo,lo+force,lo+runLen); runLen=force; } //把run放入runstack中 ts.pushRun(lo,runLen); //判断是否应该合并,i是从栈顶开始的,知道不能合并为止 //1.runLen[i-3]>runLen[i-2]+runLen[i-1] //2.runLen[i-2]>runLen[i-1] ts.mergeCollapse(); lo+=runLen; nRemaining-=runLen; }while(nRemaining!=0); //Mergeallremainingrunstocompletesort assertlo==hi; //合并剩下的run ts.mergeForceCollapse(); assertts.stackSize==1;
在看里面的一个比较重要的函数
/** *如果后2个run的长度加起来比前面一个长,则使用中间位置的run和前后长度更短的run一个合并 *如果后2个run的长度加起来比前面一个短,则把后面2个run合并 */ privatevoidmergeCollapse(){ while(stackSize>1){ intn=stackSize-2; if(n>0&&runLen[n-1]<=runLen[n]+runLen[n+1]){ if(runLen[n-1]<runLen[n+1]) n--; mergeAt(n); }elseif(runLen[n]<=runLen[n+1]){ mergeAt(n); }else{ break;//Invariantisestablished } } }