博客發(fā)表于：Ghamster Blog
轉(zhuǎn)載請(qǐng)注明出處
常見的排序算法主要包括冒泡丸相、插入拌蜘、歸并粒督、希爾以及快排陪竿，教科書上也給出了算法的簡(jiǎn)單實(shí)現(xiàn)和原理解析。在實(shí)際使用中，編程語(yǔ)言提供的排序算法族跛，通常是這些算法相結(jié)合的優(yōu)化版本
Java的排序方法集中在java.util.Arrays類闰挡，主要有三大類：
- 對(duì)基本類型數(shù)組排序算法，封裝在
java.util.DualPivotQuicksort - 對(duì)泛型數(shù)組的排序算法礁哄，封裝在
java.util.TimSort - 多線程排序方法
parallelSort
本文將結(jié)合源碼长酗，分析DualPivotQuicksort排序算法，源碼為Oracle jdk1.8 java.util.DualPivotQuicksort
DualPivotQuicksort 類
雖然這個(gè)類的名字叫做雙樞軸快排桐绒，但實(shí)際上這個(gè)類封裝了上面提到的大多數(shù)排序算法夺脾。排序方法sort可以根據(jù)一些列策略，自動(dòng)選取合適的算法對(duì)數(shù)組排序
該類定義了幾個(gè)常量：
| constant | value |
|---|---|
| QUICKSORT_THRESHOLD | 286 |
| INSERTION_SORT_THRESHOLD | 47 |
| COUNTING_SORT_THRESHOLD_FOR_BYTE | 29 |
| COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR | 3200 |
計(jì)數(shù)排序特別適合待排序數(shù)組特別長(zhǎng)茉继，類型本身可表示的值個(gè)數(shù)相對(duì)較少的情況咧叭，如
byte。與其他類型數(shù)組排序相比烁竭，byte數(shù)組的排序多了一個(gè)判斷步驟——當(dāng)數(shù)組長(zhǎng)度超過(guò)30（right-left+1）時(shí)菲茬，會(huì)觸發(fā)計(jì)數(shù)排序。由于計(jì)數(shù)排序相對(duì)簡(jiǎn)單派撕，在此不多做贅述婉弹。
以int型數(shù)組為例，sort方法有兩種簽名终吼，分別是：
-
sort(int[] a, int left, int right, int[] work, int workBase, int workLen)镀赌，訪問(wèn)權(quán)限為package，實(shí)現(xiàn)了歸并排序算法衔峰。當(dāng)數(shù)組長(zhǎng)度較短時(shí)佩脊，調(diào)用下面的方法 -
sort(int[] a, int left, int right, boolean leftmost)，訪問(wèn)權(quán)限private垫卤，實(shí)現(xiàn)了快排和插入排序
總結(jié)起來(lái)威彰，排序算法選擇策略如下（待排序數(shù)組長(zhǎng)度L）：
- L >= QUICKSORT_THRESHOLD：采用歸并排序
- L < QUICKSORT_THRESHOLD && L >= INSERTION_SORT_THRESHOLD：采用雙樞軸快排
- L < INSERTION_SORT_THRESHOLD：采用插入排序
Merge Sort
使用歸并排序的條件有三條：
- 數(shù)組長(zhǎng)度超過(guò)QUICKSORT_THRESHOLD
- 數(shù)組局部有序
- 數(shù)組不存在較多連續(xù)相等的元素
有序性判定
源碼119~148行：
int[] run = new int[MAX_RUN_COUNT + 1];
int count = 0; run[0] = left;
// Check if the array is nearly sorted
for (int k = left; k < right; run[count] = k) {
if (a[k] < a[k + 1]) { // ascending
while (++k <= right && a[k - 1] <= a[k]);
} else if (a[k] > a[k + 1]) { // descending
while (++k <= right && a[k - 1] >= a[k]);
for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
}
} else { // equal
for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
if (--m == 0) {
sort(a, left, right, true);
return;
}
}
}
/*
* The array is not highly structured,
* use Quicksort instead of merge sort.
*/
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
}
}
歸并排序優(yōu)化的基本思路是，將原數(shù)組中原本有序的子序列檢測(cè)出來(lái)穴肘，以這些子序列為初始劃分進(jìn)行排序歇盼。從而避免像傳統(tǒng)的歸并排序算法，為保證初始子序列有序评抚，子序列長(zhǎng)度只能設(shè)為1
數(shù)組run用來(lái)記錄序列中每段有序子序列的坐標(biāo)范圍豹缀，如run[0]==0 && run[1]==3表示第一段有序序列起始索引為0，終止索引為2慨代；變量count記錄已檢出的有序子序列個(gè)數(shù)
for循環(huán)檢索有序序列邢笙，并將值存儲(chǔ)到run和count：
前兩個(gè)元素遞增，檢索后續(xù)遞增元素
前兩個(gè)遞減侍匙，檢索后續(xù)遞減氮惯，然后將這段子序列reverse
前兩個(gè)相等，檢索后續(xù)相等。這里有個(gè)特殊情況妇汗，當(dāng)連續(xù)相等的元素?cái)?shù)量超過(guò)MAX_RUN_LENGTH時(shí)帘不，認(rèn)為相等元素過(guò)多，不再使用歸并杨箭，而是調(diào)用快排方法解決
當(dāng)count值超過(guò)MAX_RUN_COUNT時(shí)寞焙，同樣退出歸并，調(diào)用快排進(jìn)行排序互婿。因?yàn)?code>count過(guò)大意味著平均有序子序列較短捣郊，即數(shù)組基本無(wú)序
源碼152~156處理了一下邊界情況，當(dāng)以上for循環(huán)最后一次執(zhí)行結(jié)束后慈参，如果剛好
k==right模她，執(zhí)行遞增run[count] = k，表示發(fā)現(xiàn)一組有序序列懂牧，索引是*到right-1侈净；下一次循環(huán)條件k<right不滿足，for循環(huán)退出僧凤。但實(shí)際上畜侦，數(shù)組元素a[right]是由一個(gè)元素組成的有序序列，因?qū)?yīng)run數(shù)組末尾需要添加一個(gè)值為right+1的元素
歸并算法
歸并算法空間復(fù)雜度為O(n)躯保，即必須有和待排序數(shù)組等大的輔助數(shù)組空間旋膳。入?yún)⒌?code>work變量就是用作輔助數(shù)組，數(shù)組可用空間可以不從0索引開始途事，但必須連續(xù)验懊；workBase表示起始地址，workLen表示可用長(zhǎng)度尸变。傳入的工作數(shù)組可能為空义图，此時(shí)可以自己創(chuàng)建一個(gè)。
sort方法沒(méi)有返回值召烂，所以我們希望歸并結(jié)束時(shí)碱工，剛好數(shù)據(jù)由輔助數(shù)組復(fù)制到原數(shù)組。因此需要根據(jù)有序子序列個(gè)數(shù)計(jì)算出需要?dú)w并的次數(shù)：
byte odd = 0;
for (int n = 1; (n <<= 1) < count; odd ^= 1);
當(dāng)odd==1奏夫，即n左移2k+1次怕篷，需要?dú)w并奇數(shù)次，第一次歸并應(yīng)從輔助數(shù)組到原數(shù)組酗昼；反之亦然廊谓。源碼618~628行即處理這個(gè)問(wèn)題
源碼631~651根據(jù)run數(shù)組保存的信息執(zhí)行歸并，每輪歸并后把新的有序序列信息覆蓋到run中保存：
for (int last; count > 1; count = last) {
for (int k = (last = 0) + 2; k <= count; k += 2) {
int hi = run[k], mi = run[k - 1];
for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
b[i + bo] = a[p++ + ao];
} else {
b[i + bo] = a[q++ + ao];
}
}
run[++last] = hi;
}
if ((count & 1) != 0) {
for (int i = right, lo = run[count - 1]; --i >= lo;
b[i + bo] = a[i + ao]
);
run[++last] = right;
}
long[] t = a; a = b; b = t;
int o = ao; ao = bo; bo = o;
}
這里有幾個(gè)需要注意的點(diǎn)：由于歸并后子序列數(shù)量減半麻削，實(shí)際上run的后1/2空間還保存著原有的子序列信息蒸痹，但for循環(huán)通過(guò)count確定循環(huán)邊界舔示，所以每次歸并結(jié)束只要更新count即可；若本輪count為奇數(shù)电抚，則最后一個(gè)有序序列需要原樣復(fù)制到目標(biāo)數(shù)組中
Quick Sort
當(dāng)數(shù)組長(zhǎng)度小于QUICKSORT_THRESHOLD或上文列舉的其他合適情況時(shí)，private的排序方法sort(int[] a, int left, int right, boolean leftmost)被調(diào)用
該方法大致有四種排序邏輯：insertion sort竖共，pair insertion sort蝙叛，quick sort，dual pivot quick sort公给。前兩種用于待排序數(shù)組長(zhǎng)度小于INSERTION_SORT_THRESHOLD的情況借帘，后兩種相反。由于快排是遞歸排序淌铐，實(shí)際在排序的最后階段是由插入排序完成的
關(guān)于雙樞軸快排比傳統(tǒng)快排快的原因可以參考：Why Is Dual-Pivot Quicksort Fast?肺然，概括來(lái)說(shuō)雖然雙樞軸快排增加了比較次數(shù)同時(shí)降低了存儲(chǔ)訪問(wèn)次數(shù)。由于CPU和存儲(chǔ)速度不匹配腿准，性能瓶頸在于存儲(chǔ)际起，所以增加的比較次數(shù)影響不大，使雙樞更快
插入排序
leftmost參數(shù)吐葱，顧名思義街望，待排序子序列是否在數(shù)組最左側(cè)。leftmost為true時(shí)弟跑，使用傳統(tǒng)的插入排序（這里不再展開描述）灾前，否則使用pair insertion sort。
分析代碼孟辑，在方法觸發(fā)快排邏輯后哎甲，得到被樞分隔開的2或3個(gè)子序列排序，隨后執(zhí)行遞歸饲嗽，只有非最左側(cè)的子序列遞歸方法入?yún)?code>leftmost為false炭玫，其余所有情況都為true。因此根據(jù)快排的性質(zhì)可以確定貌虾，當(dāng)leftmost為false時(shí)础嫡，子序列中的所以元素均大于等于其左側(cè)的所有元素，所以其左側(cè)元素均可充當(dāng)守衛(wèi)酝惧，而不必每輪循環(huán)檢查索引越界
pair insertion sort源碼在253~274：
do {
if (left >= right) {
return;
}
} while (a[++left] >= a[left - 1]);
for (int k = left; ++left <= right; k = ++left) {
int a1 = a[k], a2 = a[left];
if (a1 < a2) {
a2 = a1; a1 = a[left];
}
while (a1 < a[--k]) {
a[k + 2] = a[k];
}
a[++k + 1] = a1;
while (a2 < a[--k]) {
a[k + 1] = a[k];
}
a[k + 1] = a2;
}
int last = a[right];
while (last < a[--right]) {
a[right + 1] = a[right];
}
a[right + 1] = last;
pair insertion sort改進(jìn)的思想是榴鼎，每次取兩個(gè)元素，先對(duì)較大的進(jìn)行插入排序晚唇；當(dāng)找到插入位置后巫财，由于較小插入位置一定更靠前，所以可以從當(dāng)前位置繼續(xù)執(zhí)行插入排序算法哩陕，而不用回到有序序列的尾部重新比較平项。
代碼在排序開始前do...while跳過(guò)了序列開頭已有序的部分赫舒，同時(shí)left++，這是由于上面提到左側(cè)元素可以充當(dāng)守衛(wèi)的原因闽瓢，不再需要left記錄待排序序列的起始位置
雙樞軸快排
當(dāng)待排序數(shù)組長(zhǎng)度大于INSERTION_SORT_THRESHOLD接癌，使用快排
源碼279~312行處理樞軸選擇邏輯：
- 取
seventh為待排序序列長(zhǎng)度近似1/7，e3為中點(diǎn)索引 - 取
e3向前向后seventh, 2*seventh長(zhǎng)度位置索引扣讼，最終得到e1~e5 - 對(duì)
e1~e5位置的元素執(zhí)行插入排序（這里沒(méi)用for循環(huán)缺猛，直接手寫完整插入排序，簡(jiǎn)直太暴力了） - 判等椭符，當(dāng)
e1~e5均不想等時(shí)荔燎，取e2 e4為樞，執(zhí)行dual pivot quick sort销钝；否則取e3為樞有咨，執(zhí)行普通快排（這里不在詳細(xì)描述）
雙樞軸快排原理如下：
- 快排需要兩個(gè)樞
pivot1和pivot2，三個(gè)指針(索引)less k great蒸健，三個(gè)指針將數(shù)組分為四個(gè)部分座享，參考源碼：
/*
* Partitioning:
*
* left part center part right part
* +--------------------------------------------------------------+
* | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
* +--------------------------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot1
* pivot1 <= all in [less, k) <= pivot2
* all in (great, right) > pivot2
*/
outer:
for (int k = less - 1; ++k <= great; ) {
int ak = a[k];
if (ak < pivot1) { // Move a[k] to left part
a[k] = a[less];
a[less] = ak;
++less;
} else if (ak > pivot2) { // Move a[k] to right part
while (a[great] > pivot2) {
if (great-- == k) {
break outer;
}
}
if (a[great] < pivot1) { // a[great] <= pivot2
a[k] = a[less];
a[less] = a[great];
++less;
} else { // pivot1 <= a[great] <= pivot2
a[k] = a[great];
}
a[great] = ak;
--great;
}
}
排序開始前，
less從left開始向右移動(dòng)似忧，跳過(guò)<pivot1的元素征讲；同理great向左跳過(guò)
注意邊界情況，less指示的是center part的起始位置橡娄，即pivot1<=a[less]<=pivot2
- 初始
k等于less诗箍，即center part長(zhǎng)度為0；k和great之間的元素即為待排序元素挽唉；當(dāng)k==great本輪快排結(jié)束 -
k指示的值有三種情況：-
pivot1 <= a[k] <= pivot2：a[k]屬于center part滤祖，只需執(zhí)行k++ -
a[k]<pivot1：a[k]屬于left part，a[less]和a[k]交換瓶籽，執(zhí)行less++, k++ -
a[k]>pivot2：a[k]屬于right part匠童，此時(shí)情況有些復(fù)雜。首先將great向左移動(dòng)塑顺，找到一個(gè)a[great]<=pivot2的元素汤求，分兩種情況：-
pivot1<=a[great]<=pivot2，則交換a[k]和a[great]即可严拒，然后k++, great-- -
a[great]<pivot1扬绪，首先a[great]賦值給a[less]，擴(kuò)展left part區(qū)less++裤唠；a[less]原值賦給a[k]挤牛，k++相當(dāng)于center part向右平移一個(gè)單位；a[k]原值賦給a[great]种蘸，great--
-
-
- 快排結(jié)束后墓赴，遞歸調(diào)用
sort對(duì)子序列排序
源碼中遞歸前竞膳，對(duì)于center part進(jìn)行了特殊處理——判斷less < e1 && e5 < great值，若該值為true則center part長(zhǎng)度是否超出原數(shù)組長(zhǎng)度4/7
理論上通過(guò)上述樞軸選擇策略诫硕，pivot1 pivot2應(yīng)當(dāng)將原數(shù)組分割為基本相等的三份坦辟，如果center part較大，則問(wèn)題很可能出現(xiàn)在邊界條件=上章办，即center part中有大量相等元素锉走。可以通過(guò)排除與pivot1和pivot2相等的元素纲菌，大幅減少center part中需要排序的長(zhǎng)度。這部分算法可以看作變形版的快排疮绷，參考源碼注釋：
/*
* Partitioning:
*
* left part center part right part
* +----------------------------------------------------------+
* | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
* +----------------------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (*, less) == pivot1
* pivot1 < all in [less, k) < pivot2
* all in (great, *) == pivot2
*/
隨后只對(duì)[less, k-1]遞歸即可
Conclusion
TimSort算法更神奇翰舌，有時(shí)間也寫一下
