探索起因
這里講一下我要去關(guān)注這塊源碼的起因宫盔，有助于激發(fā)興趣麦撵。
這是我在leetcode練習(xí)算法時(shí)遇到的：
給定長(zhǎng)度為 2n 的數(shù)組, 你的任務(wù)是將這些數(shù)分成 n 對(duì), 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得從1 到 n 的 min(ai, bi) 總和最大。
在解這題時(shí)，我想到的方式是排升序后，取偶數(shù)索引想加喇澡，可解，當(dāng)時(shí)也沒過多想殊校，直接上手謝了一個(gè)冒泡排序晴玖，然后再取。但是提交的時(shí)候報(bào)出超出時(shí)間限制的錯(cuò)誤为流，我當(dāng)時(shí)還一度懷疑自己的解法是否有問題呕屎，直到我去看題解時(shí)，大多數(shù)人的想法跟我一樣敬察，只不過上面解法我是靠自己推測(cè)的秀睛，而別人是有嚴(yán)格的數(shù)據(jù)公式來證明的，那我就想為什么我的不對(duì)呢莲祸，之后看了他們的代碼蹂安，他們的排序都不是自己手寫的，都用了自帶的工具類，之后我也嘗試了下改為Arrays的sort排序方法，果然也通過了贴妻。之后我就對(duì)這個(gè)方法產(chǎn)生了興趣，因?yàn)槲抑烂芭菖判蛩惴ǖ臅r(shí)間復(fù)雜度是n的平方允瞧，我想看看官方的排序算法是怎么實(shí)現(xiàn)的。
源碼解析
之后我懷著好奇的心情點(diǎn)進(jìn)了源碼蛮拔，我們首先進(jìn)入的是：
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
在這我們可以知曉真正實(shí)現(xiàn)排序的類是DualPivotQuicksort述暂，而且看名字好像是快排，那么我們繼續(xù)深入建炫。
小規(guī)模數(shù)組排序
終于我們來到了真正實(shí)現(xiàn)排序的地方畦韭，由于過程比較復(fù)雜，顧我們一部分一部分來看這內(nèi)容肛跌，首先第一步：
// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
我們可以看到廊驼，當(dāng)數(shù)組長(zhǎng)度小于QUICKSORT_THRESHOLD這個(gè)閾值時(shí)，我們將進(jìn)入的排序算法是什么惋砂？首先首先這個(gè)閾值是多少：
/**
* If the length of an array to be sorted is less than this
* constant, Quicksort is used in preference to merge sort.
*/
private static final int QUICKSORT_THRESHOLD = 286;
我們看這個(gè)注釋，看到使用的是歸并排序绳锅，我們繼續(xù)來看上面遺留的排序算法源碼西饵，這個(gè)方法也非常的長(zhǎng)，我們來進(jìn)入相關(guān)的源碼鳞芙，無關(guān)源碼我們就先不看了：
首先是：
int length = right - left + 1;
// Use insertion sort on tiny arrays
if (length < INSERTION_SORT_THRESHOLD) {
if (leftmost) {
/*
* Traditional (without sentinel) insertion sort,
* optimized for server VM, is used in case of
* the leftmost part.
*/
for (int i = left, j = i; i < right; j = ++i) {
int ai = a[i + 1];
while (ai < a[j]) {
a[j + 1] = a[j];
if (j-- == left) {
break;
}
}
a[j + 1] = ai;
}
}
這里又出現(xiàn)了INSERTION_SORT_THRESHOLD這個(gè)值眷柔，我們來看下：
/**
* If the length of an array to be sorted is less than this
* constant, insertion sort is used in preference to Quicksort.
*/
private static final int INSERTION_SORT_THRESHOLD = 47;
這里也說的非常清楚期虾，如果數(shù)組長(zhǎng)度小于這個(gè)值，我們就進(jìn)行使用插入排序驯嘱。
插入排序算法回顧
在看到這段的時(shí)候镶苞，我當(dāng)初想直接跳過，因?yàn)槲抑朗裁词遣迦肱判蚓掀溃侨送亲砸詾槭堑拿荆援?dāng)我自己按照對(duì)這個(gè)算法的理解手寫時(shí)，我沒有寫出來剃幌。
先講一下我對(duì)這個(gè)算法的理解：
我個(gè)人認(rèn)為插排和冒泡排序的動(dòng)作是相反的聋涨，插排比較適合于原本順序比較好的情況（這里有個(gè)專用詞給忘了），它是從第一個(gè)開始负乡，然后和當(dāng)前之后的元素比較牍白，如果順序一樣，則無需再做迭代抖棘，不然則從當(dāng)前開始向上迭代比較茂腥。
這里還是舉個(gè)理解比較好，也可以結(jié)合上面的源碼來進(jìn)行查看切省，假設(shè)我們給定數(shù)組[3最岗，2，1]数尿，但是我們卻是要升序排仑性，這個(gè)時(shí)候其實(shí)性能最差，迭代次數(shù)最多右蹦。
i=0, j=0, ai=a[i+1]=2,a[j]=3,因?yàn)闈M足ai<a[j]诊杆，顧a[j+1]=a[1]=3,然后j == 0,顧退出后，a[0] = 2,也就是a[0]和a[1]調(diào)換了順序何陆。
我們總結(jié)一下晨汹，就是說開始我們會(huì)拿a[i]與a[i+1]比，這時(shí)的a[i]肯定是比a[m] (m<i) 都要大的贷盲，如果是升序排序的話淘这，如果a[i+1]大于a[i]的話，就沒必要迭代了巩剖，因?yàn)楸戎暗臄?shù)肯定都大铝穷，但是如果不是，則一級(jí)級(jí)的網(wǎng)上找佳魔，找到后進(jìn)行調(diào)換位置曙聂。
不清楚大家有沒有理解，我先貼出我按照這個(gè)思路寫出的代碼鞠鲜，和官網(wǎng)的不太一樣宁脊，大家可以比較看看断国，我覺得我的比較容易理解：
for (int i = 0; i < nums.length - 1; i++) {
int tmp = nums[i+1];
int j = i;
while (j >= 0){
if (nums[j] > tmp ){
nums[j+1] = nums[j];
j--;
}else {
break;
}
}
nums[j+1] =tmp;
}
OK,到這我們把第一個(gè)算法解決了，下面的那個(gè)算法就比較有難度了榆苞。剛開始我只知道是快排稳衬，但是沒想到快排中的學(xué)問那么大，這里首先建議閱讀單軸快排（SinglePivotQuickSort）和雙軸快排（DualPivotQuickSort）及其JAVA實(shí)現(xiàn)
再次強(qiáng)調(diào)坐漏，如果對(duì)快排沒有了解過的話薄疚，強(qiáng)力建議先看上述文章了解其內(nèi)容，寫的非常好仙畦。OK输涕，了解之后我們?cè)賮砜丛贏rrays.sort中的快排實(shí)現(xiàn)。
快排實(shí)現(xiàn)
這里我們引用上面文章的一段話慨畸，講述這個(gè)算法的思想：
雙軸快速排序莱坎，顧名思義，取兩個(gè)中心點(diǎn)pivot1寸士，pivot2檐什，且pivot≤pivot2，可將序列分成三段：x<pivot1弱卡、pivot1≤x≤pivot2乃正，x<pivot2，然后分別對(duì)三段進(jìn)行遞歸婶博。
既然要兩個(gè)中心點(diǎn)瓮具，我們一般將第一個(gè)元素和最后一個(gè)元素作為兩個(gè)中心點(diǎn)。實(shí)現(xiàn)大致過程如下：
1.初始化時(shí)凡人，i=start名党，j=end，k=start+1挠轴，k負(fù)責(zé)掃描传睹。序列第一個(gè)值大于序列最后一個(gè)值，需要進(jìn)行交換岸晦。然后pivot1=items[start]欧啤，pivot2=items[end]。
2.掃描過程中保持：1~i是小于pivot1的元素启上，i~k是大于等于pivot1邢隧、小于等于pivot2的元素，j~end-1是大于pivot2的元素冈在。
上面是大致介紹了雙軸快排的基本思想府框，而java的在一定基礎(chǔ)上又做了優(yōu)化。我們一步步來深入，首先看上述思想我們知道迫靖，第一步其實(shí)要做的就是選2個(gè)中心點(diǎn)pivot1，pivot2兴使，java在這一步中的優(yōu)化我們來看下：
// Inexpensive approximation of length / 7
int seventh = (length >> 3) + (length >> 6) + 1;
/*
* Sort five evenly spaced elements around (and including) the
* center element in the range. These elements will be used for
* pivot selection as described below. The choice for spacing
* these elements was empirically determined to work well on
* a wide variety of inputs.
*/
int e3 = (left + right) >>> 1; // The midpoint
int e2 = e3 - seventh;
int e1 = e2 - seventh;
int e4 = e3 + seventh;
int e5 = e4 + seventh;
// Sort these elements using insertion sort
if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
}
if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
}
}
if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
}
}
}
// Pointers
int less = left; // The index of the first element of center part
int great = right; // The index before the first element of right part
首先要確認(rèn)系宜，能到這一步的說明數(shù)組長(zhǎng)度是大于INSERTION_SORT_THRESHOLD的長(zhǎng)度也就是47的，所以int seventh = (length >> 3) + (length >> 6) + 1; 這步說明數(shù)組長(zhǎng)度至少要7以上发魄。
接下來是5分法盹牧，通過e3為數(shù)組中間值，在根據(jù)seventh值的加減得到
下面這塊if區(qū)域可以看到我們剛開始基本沒用励幼，后面也是對(duì)e1到e5進(jìn)行排序
下面又是一個(gè)關(guān)鍵點(diǎn)：
if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
如果值都不相同的情況下我們進(jìn)行雙軸快排汰寓，如果不滿足我們來看下
else { // Partitioning with one pivot
我們就會(huì)實(shí)現(xiàn)用單軸快排
我們先來講雙軸。
快排之雙軸快排
我們先截下來所有代碼苹粟，避免讀者思路斷續(xù)
/*
* Use the second and fourth of the five sorted elements as pivots.
* These values are inexpensive approximations of the first and
* second terciles of the array. Note that pivot1 <= pivot2.
*/
int pivot1 = a[e2];
int pivot2 = a[e4];
/*
* The first and the last elements to be sorted are moved to the
* locations formerly occupied by the pivots. When partitioning
* is complete, the pivots are swapped back into their final
* positions, and excluded from subsequent sorting.
*/
a[e2] = a[left];
a[e4] = a[right];
/*
* Skip elements, which are less or greater than pivot values.
*/
while (a[++less] < pivot1);
while (a[--great] > pivot2);
/*
* 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
*
* Pointer k is the first index of ?-part.
*/
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];
/*
* Here and below we use "a[i] = b; i++;" instead
* of "a[i++] = b;" due to performance issue.
*/
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];
}
/*
* Here and below we use "a[i] = b; i--;" instead
* of "a[i--] = b;" due to performance issue.
*/
a[great] = ak;
--great;
}
}
// Swap pivots into their final positions
a[left] = a[less - 1]; a[less - 1] = pivot1;
a[right] = a[great + 1]; a[great + 1] = pivot2;
// Sort left and right parts recursively, excluding known pivots
sort(a, left, less - 2, leftmost);
sort(a, great + 2, right, false);
/*
* If center part is too large (comprises > 4/7 of the array),
* swap internal pivot values to ends.
*/
if (less < e1 && e5 < great) {
/*
* Skip elements, which are equal to pivot values.
*/
while (a[less] == pivot1) {
++less;
}
while (a[great] == pivot2) {
--great;
}
/*
* 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
*
* Pointer k is the first index of ?-part.
*/
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];
/*
* Even though a[great] equals to pivot1, the
* assignment a[less] = pivot1 may be incorrect,
* if a[great] and pivot1 are floating-point zeros
* of different signs. Therefore in float and
* double sorting methods we have to use more
* accurate assignment a[less] = a[great].
*/
a[less] = pivot1;
++less;
} else { // pivot1 < a[great] < pivot2
a[k] = a[great];
}
a[great] = ak;
--great;
}
}
}
// Sort center part recursively
sort(a, less, great, false);
- 第一步我們確定了pivot1和pivot2點(diǎn)有滑，并把它放在初始兩端
- 第二步開始掃描，在less上從左到右掃描索引值是否小于pivot1嵌削，直到遇到大于等于pivot1值暫停毛好。而great則從右到左相反。
- 第三步也就正在到了雙軸快排的地方苛秕，我們是通過移動(dòng)指針k來進(jìn)行的
- 第四步更換中心店位置肌访，并進(jìn)行雙邊排序，這里的排序用的是插入排序
- 第五步艇劫，如果中心值太多吼驶，則繼續(xù)使用快排來進(jìn)行排序，最后還是使用插入排序
總結(jié)：這里的思路都可以離清楚了店煞，但是如果讓我自己手寫可能有點(diǎn)夠嗆蟹演。不過目前我還是以理解為主。
下面開始介紹單軸快排
快排之單軸快排
我們繼續(xù)來進(jìn)行浅缸，這里老樣子我們直接貼上所有代碼：
/*
* Use the third of the five sorted elements as pivot.
* This value is inexpensive approximation of the median.
*/
int pivot = a[e3];
/*
* Partitioning degenerates to the traditional 3-way
* (or "Dutch National Flag") schema:
*
* left part center part right part
* +-------------------------------------------------+
* | < pivot | == pivot | ? | > pivot |
* +-------------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot
* all in [less, k) == pivot
* all in (great, right) > pivot
*
* Pointer k is the first index of ?-part.
*/
for (int k = less; k <= great; ++k) {
if (a[k] == pivot) {
continue;
}
int ak = a[k];
if (ak < pivot) { // Move a[k] to left part
a[k] = a[less];
a[less] = ak;
++less;
} else { // a[k] > pivot - Move a[k] to right part
while (a[great] > pivot) {
--great;
}
if (a[great] < pivot) { // a[great] <= pivot
a[k] = a[less];
a[less] = a[great];
++less;
} else { // a[great] == pivot
/*
* Even though a[great] equals to pivot, the
* assignment a[k] = pivot may be incorrect,
* if a[great] and pivot are floating-point
* zeros of different signs. Therefore in float
* and double sorting methods we have to use
* more accurate assignment a[k] = a[great].
*/
a[k] = pivot;
}
a[great] = ak;
--great;
}
}
/*
* Sort left and right parts recursively.
* All elements from center part are equal
* and, therefore, already sorted.
*/
sort(a, left, less - 1, leftmost);
sort(a, great + 1, right, false);
}
這里經(jīng)過上面雙軸排序的邏輯轨帜，這里就松松然了，比較的簡(jiǎn)單衩椒，正常的三分雙向掃描算法蚌父。
這里我們發(fā)現(xiàn)了一種情況，也就是如果在插排中我們傳入的那個(gè)boolean值是false的情況是怎樣的毛萌，我們下面的補(bǔ)充苟弛。
插排的另外一種情況
else {
/*
* Skip the longest ascending sequence.
*/
do {
if (left >= right) {
return;
}
} while (a[++left] >= a[left - 1]);
/*
* Every element from adjoining part plays the role
* of sentinel, therefore this allows us to avoid the
* left range check on each iteration. Moreover, we use
* the more optimized algorithm, so called pair insertion
* sort, which is faster (in the context of Quicksort)
* than traditional implementation of insertion sort.
*/
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;
}
return;
}
這里使用的是一種新型的pair insertion sort 結(jié)對(duì)插入算法，在原本插入算法的基礎(chǔ)上一次操作兩個(gè)元素阁将。在網(wǎng)上搜了下沒有很好的文檔說明膏秫，這里我按照自己讀的理解來進(jìn)行說明。
- 首先這個(gè)算法只適用于數(shù)組中部分排序做盅，并且排序部分的開頭不能是原數(shù)組的開頭而且數(shù)組前面部分要已經(jīng)排序好了缤削。
- 其次在這的a1和a2窘哈，因?yàn)槲覀兪巧蚺判虻模@里一開始的操作讓我有點(diǎn)霧水亭敢，這步是干嘛的滚婉？后面我想了下，如果不進(jìn)行這不排序帅刀，在掃描是a2是小于a1的让腹，那么a2就會(huì)直接插入到a1前面就不進(jìn)行繼續(xù)掃描了，這部分應(yīng)該是為了避免這步扣溺。
- 其他的我感覺就是和普通插排差不多骇窍，當(dāng)然里面的細(xì)節(jié)我沒有過多關(guān)注。
今日總結(jié)
今天的收貨還是非常滿的锥余，我們剛開始回顧了最原始的普通的插入排序腹纳，之后又經(jīng)歷的快排的雙軸快排和單軸快排，最后還經(jīng)歷了一個(gè)新型的哈恰，建立在特殊數(shù)組排序的算法只估，結(jié)對(duì)插入排序。
當(dāng)然着绷，我們也要注意蛔钙，目前這部分的排序只是針對(duì)于數(shù)組長(zhǎng)度是小于QUICKSORT_THRESHOLD數(shù)值286的，如果大于這個(gè)值呢荠医？我們將如何進(jìn)行排序呢吁脱？ 我們下次再進(jìn)行分析~~~
