当数据量大起来的时候可以看到n*log(n)以及n2，n3，2^n的时间复杂度图像都已经快成竖线了。所以在大数据面前你还在写两个for的n平方时间复杂度的暴力解法算法吗？
Arrays.sort()因为后面的双指针算法可能要先对数据排序，所以我们来研究下这里面有什么新鲜玩意。
第一层
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翻译下就好了。
讲的啥嘞，待会再看。
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，则优先使用快速排序而不是归并排序。再进去。
第三层
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个和第四个作为枢轴，而普通的快排是一个基准。
int pivot1 = a[e2]; int pivot2 = a[e4];
a[e2] = a[left]; a[e4] = a[right];
因此可以发现两枢轴，就是两个结点，把数据划分成三部分，三部分再分别递归，可参考下图。
划分成三部分：leftpart：x 根据图可知less指向 < p1 的下一个位置，great指向 > p2 的前一个位置。k 是遍历的当前位置。 再判断：A[great] < pivot1，若成立：说明great位置的数应该在< p1 的部分。 最后 上面的过程看着比较复杂，其实就是一个交换数的过程。 结束后：形成最上面的形式，三个部分再分别进行递归。 DualQuickSort代码整理： 以上是在47-286范围的数组长度时，大于286的，它会进入归并排序（Merge Sort）， 看他数组具不具备结构：实际逻辑是分组排序，每降序为一个组，像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(nlog(n))、O(n^2)。 快速排序（java实现）
p1
less 到 k -1 之间的数：p1 <= x <= p2，对变量的当前k位置出现下面三种情况：
也就是将 a[k] 移到右边。while (a[great] > pivot2) {
if (great-- == k) {
break outer;
}
}
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[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] = akpublic 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) ;
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];
}
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");
}
}
}
但在之前，它有个小动作，检查数组是否接近排序，Check if the array is nearly sorted：
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;
}
}
总结
普通冒泡排序都是O(n^2)。
双枢轴快速排序在许多数据集上提供O（nlog(n)）性能，导致其他快速排序降级为二次性能，
并且通常比传统（单枢轴）Quicksort快。
DualPivotQuicksort两枢轴快速排序
Java的Arrays.sort()方法到底用的什么排序算法
