今天看看这个经常用的函数实现原理
基于jdk1.8
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
我们就用这个为例子走一边流程：
我们可以看到其实sort它调用的是DualPivotQuicksort.sort这样一个静态方法。
这个类中，我们先看看有些常量：
* 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;
这个意思就是说在286以内的时候，arrays.sort排序是优先使用快排而不是归并排序
在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;
这个条件是用leftmore实现的，后面的是用于具有连续增长子序列的时候用的，用两个a1,a2分别表示遍历的两个相邻的数，保证a1大于a2，先找到a1应该所在的位置，在从a1位置向前找到a2的位置。
当然这一切必须保证数组长度为偶数，如果是奇数在对末尾的数进行排序。
如果大于47 则用改进过的快排。
首先将所有的数据段分为7段，
* int e3 = (left + right) >>> 1; // The midpoint
int e2 = e3 - seventh;
int e1 = e2 - seventh;
int e4 = e3 + seventh;
int e5 = e4 + seventh;
如果这五个数大小都不同
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.
*/
正如图中所写的，它其实找到了小于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;
}
}
将整个数据段分为小于pivot1 大于pivot2 以及两个之间的三个数据段
* sort(a, left, less - 2, leftmost);
sort(a, great + 2, right, false);
将第一和第三数据段排序，接着在第二段中分成等于pivot1 等于pivot2以及其他的，
再对中间的进行排序。这么一来，这种可能就排序完了。
还有一种如果五个值有相同的话，用e3作为分界线。
这个和上面的是差不多的，只是分成大于pivot 等于pivot 和小于pivot
再递归排序就好了
以上是小于286 大于286的时候用来另一种方法。
int[] run = new int[MAX_RUN_COUNT + 1];
代码中用了这个数字去衡量这个排序的数组是否具有局部有序性。
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
}
无序的情况下直接有快排就行了。
如果有序的情况下直接用归并排序。
读源码，是我们了解大神领域的一大捷径
生命不息，奋斗不止
网友评论