今天看看這個(gè)經(jīng)常用的函數(shù)實(shí)現(xiàn)原理
基于jdk1.8
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
我們就用這個(gè)為例子走一邊流程：
我們可以看到其實(shí)sort它調(diào)用的是DualPivotQuicksort.sort這樣一個(gè)靜態(tài)方法焦影。
這個(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è)意思就是說在286以內(nèi)的時(shí)候瘾晃，arrays.sort排序是優(yōu)先使用快排而不是歸并排序
在sort中苗傅，
if (length < INSERTION_SORT_THRESHOLD)
如果length小于47 那么用直接插入排序
* 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;
或者是pair insertion sort
* 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;
這個(gè)條件是用leftmore實(shí)現(xiàn)的剪况，后面的是用于具有連續(xù)增長子序列的時(shí)候用的瓢湃，用兩個(gè)a1,a2分別表示遍歷的兩個(gè)相鄰的數(shù)挤巡，保證a1大于a2秽浇，先找到a1應(yīng)該所在的位置冀膝，在從a1位置向前找到a2的位置唁奢。
當(dāng)然這一切必須保證數(shù)組長度為偶數(shù)，如果是奇數(shù)在對末尾的數(shù)進(jìn)行排序窝剖。
如果大于47 則用改進(jìn)過的快排麻掸。
首先將所有的數(shù)據(jù)段分為7段，
* int e3 = (left + right) >>> 1; // The midpoint
int e2 = e3 - seventh;
int e1 = e2 - seventh;
int e4 = e3 + seventh;
int e5 = e4 + seventh;
如果這五個(gè)數(shù)大小都不同
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.
*/
正如圖中所寫的赐纱，它其實(shí)找到了小于pivot1的臨界值和大于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];
/*
* 這段代碼是將比pivot1小的值移到左端
/
a[less] = ak;
++less;
} else if (ak > pivot2) { 移到到右端
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;
}
}
將整個(gè)數(shù)據(jù)段分為小于pivot1 大于pivot2 以及兩個(gè)之間的三個(gè)數(shù)據(jù)段
* sort(a, left, less - 2, leftmost);
sort(a, great + 2, right, false);
將第一和第三數(shù)據(jù)段排序采郎，接著在第二段中分成等于pivot1 等于pivot2以及其他的，
再對中間的進(jìn)行排序狂魔。這么一來蒜埋，這種可能就排序完了。
還有一種如果五個(gè)值有相同的話最楷，用e3作為分界線整份。
這個(gè)和上面的是差不多的，只是分成大于pivot 等于pivot 和小于pivot
再遞歸排序就好了
以上是小于286 大于286的時(shí)候用來另一種方法籽孙。
int[] run = new int[MAX_RUN_COUNT + 1];
代碼中用了這個(gè)數(shù)字去衡量這個(gè)排序的數(shù)組是否具有局部有序性烈评。
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
}
無序的情況下直接有快排就行了。
如果有序的情況下直接用歸并排序犯建。
讀源碼讲冠，是我們了解大神領(lǐng)域的一大捷徑
生命不息，奮斗不止
