时间复杂度差距
当数据量大起来的时候可以看到n*log(n)以及n^2，n^3，2^n的时间复杂度图像都已经快成竖线了。所以在大数据面前你还在写两个for的n平方时间复杂度的暴力解法算法吗？
Arrays.sort()
因为后面的双指针算法可能要先对数据排序，所以我们来研究下这里面有什么新鲜玩意。
第一层
/**
* 将指定的数组按数字升序排序。
*
* 实现说明：排序算法是 Vladimir Yaroslavskiy、Jon Bentley 和
* Joshua Bloch 的双枢轴快速排序。 该算法在许多数据集上提供 O(n log(n)) 性能，
* 导致其他快速排序降级为二次性能，并且通常比传统（单轴）快速排序实现更快。
*
* @param a 要排序的数组
*/
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}好家伙，双枢轴快速排序DualPivotQuicksort，上官方文档：
https://cdn.rawchen.com/2021/10/time-complexity/DualPivotQuicksort.pdf
我也就不给翻译后的了，随便一个比如网易有道ORC翻译下就好了。
讲的啥嘞，待会再看。
第二层
/**
* 使用给定的数组对指定的范围进行排序
* 如果可能的话，工作区数组切片用于合并
*
* @param a 要排序的数组
* @param 将第一个元素(包括第一个元素)的索引留作排序
* @param 右边是要排序的最后一个元素(包括)的索引
* @param 工作空间数组(切片)
* @param 工作数组中可用空间的起点
* @param workLen工作数组的可用大小
*/
static void sort(int[] a, int left, int right,
int[] work, int workBase, int workLen) {
// 对小数组使用快速排序
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
...
}如果要排序的数组长度小于该常量QUICKSORT_THRESHOLD为286，则优先使用快速排序而不是归并排序。再进去。
第三层
/**
* 按双枢轴快速排序对指定范围的数组进行排序。
*
* @param a 要排序的数组
* @param left 要排序的第一个元素(包括第一个元素)的索引
* @param right 要排序的最后一个元素(包括)的索引
* @param leftmost 指示该部分是否在范围的最左边
*/
private static void sort(int[] a, int left, int right, boolean leftmost) {
int length = right - left + 1;
// 在微小数组上使用插入排序
if (length < INSERTION_SORT_THRESHOLD) {
if (leftmost) {
/*
* 传统的(没有标记的)插入排序，
* 为服务器虚拟机优化，用于最左边部分。
*/
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;
}
} else {
...
}
...
}
...
}如果要排序的数组长度小于该常量INSERTION_SORT_THRESHOLD为47，则优先使用插入排序而不是快速排序。
在47-286范围的数组长度时则对数列挑出5个基准数（pivot），至于怎么挑出的就是佛系数学啦：
int[] arr = new int[200];
int length = arr.length;
int left = 0;
int right = arr.length - 1;
//廉价的近似 length / 7
int seventh = (length >> 3) + (length >> 6) + 1;
int e3 = (left + right) >>> 1; // 中点
int e2 = e3 - seventh;
int e1 = e2 - seventh;
int e4 = e3 + seventh;
int e5 = e4 + seventh;试了下200位的基准为：41-70-99-128-157
使用插入排序对5个基准元素进行硬核排序。
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; }
}
}
}快速排序算法
往下看前先回顾下我们的快排算法。
public static void quickSort(int[] arr, int low, int high) {
int l, h, temp, t;
if (low > high) return;
l = low;
h = high;
//temp就是基准位，数组第一位
temp = arr[l];
while (l < h) {
//先看右边，依次往左递减
while (temp <= arr[h] && l < h) h--;
//再看左边，依次往右递增
while (temp >= arr[l] && l < h) l++;
//如果满足条件则交换
if (l < h) {
t = arr[h];
arr[h] = arr[l];
arr[l] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[l];
arr[l] = temp;
//递归调用左半数组
quickSort(arr, low, h - 1);
//递归调用右半数组
quickSort(arr, h + 1, high);
}快速排序通过一趟排序将待排记录分隔成独立的两部分，其中的一部分比基准小，后一部分比基准大，然后再对这前后的两部分分别采用这种方式进行排序，通过递归的运算最终达到整个序列有序。使用到二分思想和分治思想。相比如普通冒泡，它会跳着比较并交换。
双枢轴快速排序
回顾完后接着刚才的快速排序算法，再接着看双枢轴快速排序。
五个基准位取了第2个和第四个作为枢轴，而普通的快排是一个基准。
/*
* 使用五个已排序元素中的第二个和第四个作为枢轴。
* 这些值是阵列的第一和第二第三圈的廉价近似。请注意pivot1 <= pivot2。
*/
int pivot1 = a[e2];
int pivot2 = a[e4];/*
* 要排序的第一个和最后一个元素被移动到以前由枢轴占据的位置。
* 分区完成后，枢轴被交换回其最终位置，并从后续排序中排除。
*/
a[e2] = a[left];
a[e4] = a[right];因此可以发现两枢轴，就是两个结点，把数据划分成三部分，三部分再分别递归，可参考下图。
/*
* Partitioning:
*
* left part center part right part
* +--------------------------------------------------------------+
* | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
* +--------------------------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* 不变性:
*
* all in (left, less) < pivot1
* pivot1 <= all in [less, k) <= pivot2
* all in (great, right) > pivot2
*
* Pointer k is the first index of ?-part.
*/划分成三部分：leftpart：x<p1，centerpart：p1<=x<=p2，rightpart:x>p2
p1<p2，因为上面排过序。
根据图可知less指向 < p1 的下一个位置，great指向 > p2 的前一个位置。k 是遍历的当前位置。
less 到 k -1 之间的数：p1 <= x <= p2，对变量的当前k位置出现下面三种情况：
- ak < p1 交换 k 和less位置的数，less++
- ak < p1 && ak > p2 这个时候需要将 ak这个数放到对应的great的位置
也就是将 a[k] 移到右边。
while (a[great] > pivot2) {
if (great-- == k) {
break outer;
}
}再判断：A[great] < pivot1，若成立：说明great位置的数应该在< p1 的部分。
if (a[great] < pivot1) { // a[great] <= pivot2
a[k] = a[less]; // less放到 k的位置, k 位置的元素数保存在 ak中
a[less] = a[great]; // great 放到less的位置
++less; // 更新 less
} else { // pivot1 <= a[great] <= pivot2
a[k] = a[great];
}最后
/*
* 这里和下面我们使用 “a[i] = b; i--;”而不是“a[i--] = b;”由于性能问题。
*/
a[great] = ak; // ak 放到 great位置
--great;上面的过程看着比较复杂，其实就是一个交换数的过程。
若：A[great] < pivot1
则：A[less]位置说应该在中间部分，这里可以放到k的位置
则：A[great]应该放到less位置
又：ak这个数放到对应的great的位置，最后上面程序已经有了
若：A[great] >= pivot1 又：A[great] <= pivot2
则：A[k] = A[great];
则：A[great] = ak
结束后：形成最上面的形式，三个部分再分别进行递归。
DualQuickSort代码整理：
public class DualQuickSort {
public void dualQuickSort(int[] arr, int left, int right) {
if (left >= right) return;
if (arr[left] > arr[right]) {
swap(arr, left, right);
}
int less = left;
int great = right;
int pivot1 = arr[left];
int pivot2 = arr[right];
while (arr[++less] < pivot1) ;
while (arr[--great] > pivot2) ;
/*
* 分区:
*
* left part center part right part
* +--------------------------------------------------------------+
* | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
* +--------------------------------------------------------------+
* ^ ^ ^
* | | |
* less k great
* 不变性:
* 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 = arr[k];
if (ak < pivot1) { // ak 小于 p1
swap(arr, k, less); // 交换
less++;
} else if (ak > pivot2) { // ak > p2
while (arr[great] > pivot2) { // 找到不满足条件的位置
if (great-- == k) {
System.out.println("outer");
break outer;
}
}
if (arr[great] < pivot1) { // arr[great] <= pivot1，
arr[k] = arr[less]; // less放到 k的位置, k 位置的元素数保存在 ak中
arr[less] = arr[great]; // great 放到less的位置
++less; // 更新 less
} else { // pivot1 <= arr[great] <= pivot2
arr[k] = arr[great];
}
/*
* 这里和下面我们使用 “a[i] = b; i--;”而不是“a[i--] = b;”由于性能问题。
*/
arr[great] = ak; // ak 放到 great位置
--great;
} // 其他情况就是中间位置，不用考虑
}
System.out.println("left: " + left + " less: " + less + " great: " + great + " right: " + right);
for (int t : arr) {
System.out.print(t + "\t");
}
System.out.println("\n");
dualQuickSort(arr, left, less - 1);
dualQuickSort(arr, less, great);
dualQuickSort(arr, great + 1, right);
}
public void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
int[] arr = new int[]{13, 3, 65, 97, 76, 10, 35, 71, 5, 7, 3, 27, 49};
for (int t : arr) {
System.out.print(t + "\t");
}
System.out.println("\n");
int l = 0;
int r = arr.length - 1;
new DualQuickSort().dualQuickSort(arr, l, r);
for (int t : arr) {
System.out.print(t + "\t");
}
}
}以上是在47-286范围的数组长度时，大于286的，它会进入归并排序（Merge Sort），
但在之前，它有个小动作，检查数组是否接近排序，Check if the array is nearly sorted：
/*
* 索引 run[i] 是第 i 次运行的开始（升序或降序）。
*/
int[] run = new int[MAX_RUN_COUNT + 1];
int count = 0; run[0] = left;
// 检查数组是否接近排序
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;
}
}
}
/*
* 数组不是高度结构化的，使用快速排序代替归并排序。
*/
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
}
}看他数组具不具备结构：实际逻辑是分组排序，每降序为一个组，像1,9,8,7,6,8。9到6是降序，为一个组，然后把降序的一组排成升序：1,6,7,8,9,8。然后最后的8后面继续往后面找。每遇到这样一个降序组，++count，当检查中发现至少有67组就直接快速排序了，不然就说明这个数组没有太多降序组结构，就继续往下走归并排序。
三重态快速排序
查了还有更快的基于C/C++库的Triple State QuickSort
https://cdn.rawchen.com/2021/10/time-complexity/TripleStateQuickSort.pdf
总结
快排中平均时间复杂度和最坏时间复杂度分别是O(n*log(n))、O(n^2)。
普通冒泡排序都是O(n^2)。
双枢轴快速排序在许多数据集上提供O（n*log(n)）性能，导致其他快速排序降级为二次性能，
并且通常比传统（单枢轴）Quicksort快。
引用
快速排序（java实现）
DualPivotQuicksort两枢轴快速排序
Java的Arrays.sort()方法到底用的什么排序算法
