Java怎么實現排序算法Timsort
這篇文章主要介紹“Java怎么實現排序算法Timsort”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“Java怎么實現排序算法Timsort”文章能幫助大家解決問題。
背景
Timsort 是一個混合、穩定的排序算法，簡單來說就是歸并排序和二分插入排序算法的混合體，號稱世界上最好的排序算法。Timsort一直是 Python 的標準排序算法。Java SE 7 后添加了Timsort API ，我們從Arrays.sort可以看出它已經是非原始類型數組的默認排序算法了。所以不管是進階編程學習還是面試，理解 Timsort 是比較重要。
//?List?sort()????
default?void?sort(Comparator<??super?E>?c)?{
????????Object[]?a?=?this.toArray();
??????????????//數組排序
????????Arrays.sort(a,?(Comparator)?c);
??????????????...
????}
//?Arrays.sort
????public?static?<T>?void?sort(T[]?a,?Comparator<??super?T>?c)?{
????????if?(c?==?null)?{
????????????sort(a);
????????}?else?{
??????????????//?廢棄版本
????????????if?(LegacyMergeSort.userRequested)
????????????????legacyMergeSort(a,?c);
????????????else
????????????????TimSort.sort(a,?0,?a.length,?c,?null,?0,?0);
????????}
????}
????public?static?void?sort(Object[]?a)?{
????????if?(LegacyMergeSort.userRequested)
????????????legacyMergeSort(a);
????????else
????????????ComparableTimSort.sort(a,?0,?a.length,?null,?0,?0);
????}
前置知識
理解 Timsort 需要先回顧下面的知識。
指數搜索
指數搜索，也被稱為加倍搜索，是一種用于在大型數組中搜索元素而創建的算法。它是一個兩步走的過程。首先，該算法試圖找到目標元素存在的范圍?(L，R)，然后在這個范圍內使用二叉搜索來尋找目標的準確位置。時間復雜度為O(lgn)。該搜索算法在大量有序數組中比較有效。
二分插入排序
插入排序算法很簡單，大體過程是從第二個元素開始，依次向前移動交換元素直到找到合適的位置。
插入排序最優時間復雜度也要O(n)?，我們可以使用二分查找來減少插入時元素的比較次數，將時間復雜度降為logn。但是注意，二分查找插入排序仍然需要移動相同數量的元素，但是復制數組的時間消耗低于逐一互換操作。
特點：二分插入排序主要優點是在小數據集場景下排序效率很高。
public?static?int[]?sort(int[]?arr)?throws?Exception?{
????????//?開始遍歷第一個元素后的所有元素
????????for?(int?i?=?1;?i?<?arr.length;?i++)?{
????????????//?需要插入的元素
????????????int?tmp?=?arr[i];
????????????//?從已排序最后一個元素開始，如果當前元素比插入元素大，就往后移動
????????????int?j?=?i;
????????????while?(j?>?0?&&?tmp?<?arr[j?-?1])?{
????????????????arr[j]?=?arr[j?-?1];
????????????????j--;
????????????}
????????????//?將元素插入
????????????if?(j?!=?i)?{
????????????????arr[j]?=?tmp;
????????????}
????????}
????????return?arr;
????}
????public?static?int[]?binarySort(int[]?arr)?throws?Exception?{
????????for?(int?i?=?1;?i?<?arr.length;?i++)?{
????????????//?需要插入的元素
????????????int?tmp?=?arr[i];
????????????//?通過二分查找直接找到插入位置
????????????int?j?=?Math.abs(Arrays.binarySearch(arr,?0,?i,?tmp)?+?1);
????????????//?找到插入位置后，通過數組復制向后移動，騰出元素位置
????????????System.arraycopy(arr,?j,?arr,?j?+?1,?i?-?j);
????????????//?將元素插入
????????????arr[j]?=?tmp;
????????}
????????return?arr;
????}
歸并排序
歸并排序是利用分治策略的算法，包含兩個主要的操作：分割與合并。大體過程是，通過遞歸將數組不斷分成兩半，一直到無法再分割（也就是數組為空或只剩一個元素），然后進行合并排序。簡單來說合并操作就是不斷取兩個較小的排序數組然后將它們組合成一個更大的數組。
特點：歸并排序主要為大數據集場景設計的排序算法。
public?static?void?mergeSortRecursive(int[]?arr,?int[]?result,?int?start,?int?end)?{
????????//?跳出遞歸
????????if?(start?>=?end)?{
????????????return;
????????}
????????//?待分割的數組長度
????????int?len?=?end?-?start;
????????int?mid?=?(len?>>?1)?+?start;
????????int?left?=?start;?//?左子數組開始索引
????????int?right?=?mid?+?1;?//?右子數組開始索引
????????//?遞歸切割左子數組，直到只有一個元素
????????mergeSortRecursive(arr,?result,?left,?mid);
????????//?遞歸切割右子數組，直到只有一個元素
????????mergeSortRecursive(arr,?result,?right,?end);
????????int?k?=?start;
????????while?(left?<=?mid?&&?right?<=?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];
????????}
????}
????public?static?int[]?merge_sort(int[]?arr)?{
????????int?len?=?arr.length;
????????int[]?result?=?new?int[len];
????????mergeSortRecursive(arr,?result,?0,?len?-?1);
????????return?arr;
????}
Timsort 執行過程
算法大體過程，如果數組長度小于指定閥值（MIN_MERGE）直接使用二分插入算法完成排序，否則執行下面步驟：
先從數組左邊開始，執行升序運行得到一個子序列。
將這個子序列放入運行堆棧里，等待執行合并。
檢查運行堆棧里的子序列，如果滿足合并條件則執行合并。
重復第一個步驟，執行下一個升序運行。
升序運行
升序運行就是從數組查找一段連續遞增（升序）或遞減（降序）子序列的過程，如果子序列為降序則將它反轉為升序，也可以將這個過程簡稱為?run。比如數組 [2,3,6,4,9,30]，可以查找到三個子序列，[2,3,6]、[4,9]、[30]，或說3個?run。
幾個關鍵閥值
MIN_MERGE
這是個常數值，可以簡單理解為執行歸并的最小閥值，如果整個數組長度小于它，就沒必要執行那么復雜的排序，直接二分插入就行了。在 Tim Peter 的 C 實現中為 64，但實際經驗中設置為 32 效果更好，所以 java 里面此值為 32。
降序反轉時為保證穩定性，相同元素不會被顛倒。
minrun
在合并序列的時候，如果?run?數量等于或者略小于 2 的冪次方的時候，合并效率最高；如果略大于 2 的冪次方，效率就會顯著降低。所以為了提高合并效率，需要盡量控制每個?run?的長度，通過定義一個?minrun?來表示每個?run?的最小長度，如果長度太短，就用二分插入排序把?run?后面的元素插入到前面的?run?里面。
一般在執行排序算法之前，會先計算出這個 minrun（它是根據數據的特點來進行自我調整），minrun 會從32到64選擇一個數字，因此數據的大小除以 minrun 等于或略小于 2 的冪次方。比如長度是 65 ，那么 minrun 的值就是 33；如果長度是 165，minrun 就是 42。
看下 Java 里面的實現，如果數據長度（n） < MIN_MERGE，則返回數據長度。如果數據長度恰好是 2 的冪次方，則返回MIN_MERGE/2
也就是16，否則返回一個MIN_MERGE/2 <= k <= MIN_MERGE范圍的值k，這樣可以使的 n/k 接近但嚴格小于 2 的冪次方。
private?static?int?minRunLength(int?n)?{
????????assert?n?>=?0;
????????int?r?=?0;??????//?如果低位任何一位是1，就會變成1
????????while?(n?>=?MIN_MERGE)?{
????????????r?|=?(n?&?1);
????????????n?>>=?1;
????????}
????????return?n?+?r;
????}
MIN_GALLOP
MIN_GALLOP 是為了優化合并的過程設定的一個閾值，控制進入?GALLOP?模式中，?GALLOP?模式放在后面講。
下面是 Timsort 執行流程圖
運行合并
當棧里面的?run?滿足合并條件時，它就將棧里面相鄰的兩個run 進行合并。
合并條件
Timsort 為了執行平衡合并（讓合并的 run 大小盡可能相同），制定了一個合并規則，對于在棧頂的三個run，分別用X、Y 和 Z 表示他們的長度，其中 X 在棧頂，它們必須始終維持一下的兩個規則：
一旦有其中的一個條件不被滿足，則將 Y 與 X 或 Z 中的較小者合并生成新的?run，并再次檢查棧頂是否仍然滿足條件。如果不滿足則會繼續進行合并，直至棧頂的三個元素都滿足這兩個條件，如果只剩兩個run，則滿足 Y > X 即可。
如下下圖例子
當 Z <= Y+X ，將 X+Y 合并，此時只剩下兩個run。
檢測 Y < X ，執行合并，此時只剩下 X，則退出合并檢測。
我們看下 Java 里面的合并實現
private?void?mergeCollapse()?{
??????
???????//?當存在兩個以上run執行合并檢查
????????while?(stackSize?>?1)?{
??????????//?表示?Y
????????????int?n?=?stackSize?-?2;?
???????????
??????????//?Z?<=?Y?+?X?
????????????if?(n?>?0?&&?runLen[n-1]?<=?runLen[n]?+?runLen[n+1])?{?
??????????????//?如果?Z?<?X?合并Z+Y?，否則合并X+Y
??????????????if?(runLen[n?-?1]?<?runLen[n?+?1])
????????????????????n--;
????????????????
????????????????//?合并相鄰的兩個run，也就是runLen[n]?和?runLen[n+1]
????????????????mergeAt(n);?
????????????}?else?if?(runLen[n]?<=?runLen[n?+?1])?{
????????????????
????????????????//?Y?<=?X?合并?Y+X
????????????????mergeAt(n);
????????????}?else?{
????????????????
????????????????//?滿足兩個條件，跳出循環
????????????????break;?
????????????}
????????}
????}
合并內存開銷
原始歸并排序空間復雜度是?O(n)也就是數據大小。為了實現中間項，Timsort 進行了一次歸并排序，時間開銷和空間開銷都比?O(n)小。
優化是為了盡可能減少數據移動，占用更少的臨時內存，先找出需要移動的元素，然后將較小序列復制到臨時內存，在按最終順序排序并填充到組合序列中。
比如我們需要合并 X [1, 2, 3, 6, 10] 和 Y [4, 5, 7, 9, 12, 14, 17]，X 中最大元素是10，我們可以通過二分查找確定，它需要插入到 Y 的第 5個位置才能保證順序，而 Y 中最小元素是4，它需要插入到 X 中的第4個位置才能保證順序，那么就知道了[1, 2, 3] 和 [12, 14, 17] 不需要移動，我們只需要移動 [6, 10] 和 [4, 5, 7, 9]，然后只需要分配一個大小為 2 臨時存儲就可以了。
合并優化
在歸并排序算法中合并兩個數組需要一一比較每個元素，為了優化合并的過程，設定了一個閾值 MIN_GALLOP，當B中元素向A合并時，如果A中連續 MIN_GALLOP 個元素比B中某一個元素要小，那么就進入GALLOP模式。
根據基準測試，比如當A中連續7個以上元素比B中某一元素小時切入該模式效果才好，所以初始值為7。
當進入GALLOP模式后，搜索算法變為指數搜索，分為兩個步驟，比如想確定 A 中元素x在 B 中確定的位置
首先在 B 中找到合適的索引區間(2k−1,2k+1−1)?使得 x 元素在這個范圍內；
然后在第一步找到的范圍內通過二分搜索來找到對應的位置。
只有當一次運行的初始元素不是另一次運行的前七個元素之一時，馳騁才是有益的。這意味著初始閾值為 7。
關于“Java怎么實現排序算法Timsort”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注蝸牛博客行業資訊頻道，小編每天都會為大家更新不同的知識點。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：niceseo99@gmail.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
評論