Java實現(xiàn)世界上最快的排序算法Timsort的示例代碼

第Java實現(xiàn)世界上最快的排序算法Timsort的示例代碼目錄背景前置知識指數(shù)搜索二分插入排序歸并排序Timsort執(zhí)行過程升序運(yùn)行幾個關(guān)鍵閥值運(yùn)行合并合并條件合并內(nèi)存開銷合并優(yōu)化

背景

Timsort是一個混合、穩(wěn)定的排序算法，簡單來說就是歸并排序和二分插入排序算法的混合體，號稱世界上最好的排序算法。Timsort一直是Python的標(biāo)準(zhǔn)排序算法。JavaSE7后添加了TimsortAPI，我們從Arrays.sort可以看出它已經(jīng)是非原始類型數(shù)組的默認(rèn)排序算法了。所以不管是進(jìn)階編程學(xué)習(xí)還是面試，理解Timsort是比較重要。

//Listsort()

defaultvoidsort(ComparatorsuperEc){

Object[]a=this.toArray();

//數(shù)組排序

Arrays.sort(a,(Comparator)c);

//Arrays.sort

publicstaticTvoidsort(T[]a,ComparatorsuperTc){

if(c==null){

sort(a);

}else{

//廢棄版本

if(LegacyMergeSort.userRequested)

legacyMergeSort(a,c);

else

TimSort.sort(a,0,a.length,c,null,0,0);

publicstaticvoidsort(Object[]a){

if(LegacyMergeSort.userRequested)

legacyMergeSort(a);

else

ComparableTimSort.sort(a,0,a.length,null,0,0);

}

前置知識

理解Timsort需要先回顧下面的知識。

指數(shù)搜索

指數(shù)搜索，也被稱為加倍搜索，是一種用于在大型數(shù)組中搜索元素而創(chuàng)建的算法。它是一個兩步走的過程。首先，該算法試圖找到目標(biāo)元素存在的范圍(L，R)，然后在這個范圍內(nèi)使用二叉搜索來尋找目標(biāo)的準(zhǔn)確位置。時間復(fù)雜度為O(lgn)。該搜索算法在大量有序數(shù)組中比較有效。

二分插入排序

插入排序算法很簡單，大體過程是從第二個元素開始，依次向前移動交換元素直到找到合適的位置。

插入排序最優(yōu)時間復(fù)雜度也要O(n)，我們可以使用二分查找來減少插入時元素的比較次數(shù)，將時間復(fù)雜度降為logn。但是注意，二分查找插入排序仍然需要移動相同數(shù)量的元素，但是復(fù)制數(shù)組的時間消耗低于逐一互換操作。

特點：二分插入排序主要優(yōu)點是在小數(shù)據(jù)集場景下排序效率很高。

publicstaticint[]sort(int[]arr)throwsException{

//開始遍歷第一個元素后的所有元素

for(inti=1;iarr.length;i++){

//需要插入的元素

inttmp=arr[i];

//從已排序最后一個元素開始，如果當(dāng)前元素比插入元素大，就往后移動

intj=i;

while(j0tmparr[j-1]){

arr[j]=arr[j-1];

j--;

//將元素插入

if(j!=i){

arr[j]=tmp;

returnarr;

publicstaticint[]binarySort(int[]arr)throwsException{

for(inti=1;iarr.length;i++){

//需要插入的元素

inttmp=arr[i];

//通過二分查找直接找到插入位置

intj=Math.abs(Arrays.binarySearch(arr,0,i,tmp)+1);

//找到插入位置后，通過數(shù)組復(fù)制向后移動，騰出元素位置

System.arraycopy(arr,j,arr,j+1,i-j);

//將元素插入

arr[j]=tmp;

returnarr;

}

歸并排序

歸并排序是利用分治策略的算法，包含兩個主要的操作：分割與合并。大體過程是，通過遞歸將數(shù)組不斷分成兩半，一直到無法再分割（也就是數(shù)組為空或只剩一個元素），然后進(jìn)行合并排序。簡單來說合并操作就是不斷取兩個較小的排序數(shù)組然后將它們組合成一個更大的數(shù)組。

特點：歸并排序主要為大數(shù)據(jù)集場景設(shè)計的排序算法。

publicstaticvoidmergeSortRecursive(int[]arr,int[]result,intstart,intend){

//跳出遞歸

if(start=end){

return;

//待分割的數(shù)組長度

intlen=end-start;

intmid=(len1)+start;

intleft=start;//左子數(shù)組開始索引

intright=mid+1;//右子數(shù)組開始索引

//遞歸切割左子數(shù)組，直到只有一個元素

mergeSortRecursive(arr,result,left,mid);

//遞歸切割右子數(shù)組，直到只有一個元素

mergeSortRecursive(arr,result,right,end);

intk=start;

while(left=midright=end){

result[k++]=arr[left]arr[right]arr[left++]:arr[right++];

while(left=mid){

result[k++]=arr[left++];

while(right=end){

result[k++]=arr[right++];

for(k=start;k=end;k++){

arr[k]=result[k];

publicstaticint[]merge_sort(int[]arr){

intlen=arr.length;

int[]result=newint[len];

mergeSortRecursive(arr,result,0,len-1);

returnarr;

}

Timsort執(zhí)行過程

算法大體過程，如果數(shù)組長度小于指定閥值（MIN_MERGE）直接使用二分插入算法完成排序，否則執(zhí)行下面步驟：

先從數(shù)組左邊開始，執(zhí)行升序運(yùn)行得到一個子序列。將這個子序列放入運(yùn)行堆棧里，等待執(zhí)行合并。檢查運(yùn)行堆棧里的子序列，如果滿足合并條件則執(zhí)行合并。重復(fù)第一個步驟，執(zhí)行下一個升序運(yùn)行。

升序運(yùn)行

升序運(yùn)行就是從數(shù)組查找一段連續(xù)遞增（升序）或遞減（降序）子序列的過程，如果子序列為降序則將它反轉(zhuǎn)為升序，也可以將這個過程簡稱為run。比如數(shù)組[2,3,6,4,9,30]，可以查找到三個子序列，[2,3,6]、[4,9]、[30]，或說3個run。

幾個關(guān)鍵閥值

MIN_MERGE

這是個常數(shù)值，可以簡單理解為執(zhí)行歸并的最小閥值，如果整個數(shù)組長度小于它，就沒必要執(zhí)行那么復(fù)雜的排序，直接二分插入就行了。在TimPeter的C實現(xiàn)中為64，但實際經(jīng)驗中設(shè)置為32效果更好，所以java里面此值為32。

降序反轉(zhuǎn)時為保證穩(wěn)定性，相同元素不會被顛倒。

minrun

在合并序列的時候，如果run數(shù)量等于或者略小于2的冪次方的時候，合并效率最高；如果略大于2的冪次方，效率就會顯著降低。所以為了提高合并效率，需要盡量控制每個run的長度，通過定義一個minrun來表示每個run的最小長度，如果長度太短，就用二分插入排序把run后面的元素插入到前面的run里面。

一般在執(zhí)行排序算法之前，會先計算出這個minrun（它是根據(jù)數(shù)據(jù)的特點來進(jìn)行自我調(diào)整），minrun會從32到64選擇一個數(shù)字，因此數(shù)據(jù)的大小除以minrun等于或略小于2的冪次方。比如長度是65，那么minrun的值就是33；如果長度是165，minrun就是42。

看下Java里面的實現(xiàn)，如果數(shù)據(jù)長度（n）MIN_MERGE，則返回數(shù)據(jù)長度。如果數(shù)據(jù)長度恰好是2的冪次方，則返回MIN_MERGE/2

也就是16，否則返回一個MIN_MERGE/2=k=MIN_MERGE范圍的值k，這樣可以使的n/k接近但嚴(yán)格小于2的冪次方。

privatestaticintminRunLength(intn){

assertn

intr=0;//如果低位任何一位是1，就會變成1

while(n=MIN_MERGE){

r|=(n1);

n=1;

returnn+r;

}

MIN_GALLOP

MIN_GALLOP是為了優(yōu)化合并的過程設(shè)定的一個閾值，控制進(jìn)入GALLOP模式中，GALLOP模式放在后面講。

下面是Timsort執(zhí)行流程圖

運(yùn)行合并

當(dāng)棧里面的run滿足合并條件時，它就將棧里面相鄰的兩個run進(jìn)行合并。

合并條件

Timsort為了執(zhí)行平衡合并（讓合并的run大小盡可能相同），制定了一個合并規(guī)則，對于在棧頂?shù)娜齻€run，分別用X、Y和Z表示他們的長度，其中X在棧頂，它們必須始終維持一下的兩個規(guī)則：

一旦有其中的一個條件不被滿足，則將Y與X或Z中的較小者合并生成新的run，并再次檢查棧頂是否仍然滿足條件。如果不滿足則會繼續(xù)進(jìn)行合并，直至棧頂?shù)娜齻€元素都滿足這兩個條件，如果只剩兩個run，則滿足YX即可。

如下下圖例子

當(dāng)Z=Y+X，將X+Y合并，此時只剩下兩個run。檢測YX，執(zhí)行合并，此時只剩下X，則退出合并檢測。

我們看下Java里面的合并實現(xiàn)

privatevoidmergeCollapse(){

//當(dāng)存在兩個以上run執(zhí)行合并檢查

while(stackSize1){

//表示Y

intn=stackSize-2;

//Z=Y+X

if(n0runLen[n-1]=runLen[n]+runLen[n+1]){

//如果ZX合并Z+Y，否則合并X+Y

if(runLen[n-1]runLen[n+1])

n--;

//合并相鄰的兩個run，也就是runLen[n]和runLen[n+1]

mergeAt(n);

}elseif(runLen[n]=runLen[n+1]){

//Y=X合并Y+X

mergeAt(n);

}else{

//滿足兩個條件，跳出循環(huán)

break;

}

合并內(nèi)存開銷

原始?xì)w并排序空間復(fù)雜度是O(n)也就是數(shù)據(jù)大小。為了實現(xiàn)中間項，Timsort進(jìn)行了一次歸并排序，時間開銷和空間開銷都比O(n)小。

優(yōu)化是為了盡可能減少數(shù)據(jù)移動，占用更少的臨時內(nèi)存，先找出需要移動的元素，然后將較小序列復(fù)制到臨時內(nèi)存，在按最終順序排序并填充到組合序列中。

比如我們需要合并X[1,2,3,6,10]和Y[4,5,7,9,12,14,17]，X中最大元素是10，我們可以通過二分查找確定，它需要插入到Y(jié)的第5個位置才能保證順序，而Y中最小元素是4，它需要插入到X中的第4個位置才能保證順序，那么就知道了[1,2,3]和[12,14,17]不需要移動，我們只需要移動[6,10]和[4,5,7,9]，然后只需要分配一個大小為2臨時存儲就可以了。

合并優(yōu)化

在歸并排序算法中合并兩個數(shù)組需要一一比較每個元素，為了優(yōu)化合并的過程，設(shè)定了一個閾值MIN_GALLOP，當(dāng)B中元素向A合并時，如果A中連續(xù)MIN_GALLOP個元素比B中某一個元素要小，那么就進(jìn)入GALLOP模式。

根據(jù)基準(zhǔn)測試，比如當(dāng)A中連續(xù)7