/*
* java1.7之后的版本，开始用双轴快排取代了以前的排序算法，现在只实现了8种基本数据类型性的双轴快排，对象的排序在1.7中还
* 在用老式的，不过都标了过时，估计以后版本中就会被新的双轴快排取代了。
* 他的DualPivotQuicksort()方法，里边一共写了三种算法（不算改进版的插入排序话），对于大数组而且部分高度有序的用归并排序，其余的用双轴快排进行分割
* 分割到足够小的时候用插入排序（主要是改进版的pair insertion sort）。双轴快排的基本原理是取两个pivot，所有比pivot1小的放到最左边，比pivot2
* 大的放到最右边，然后递归下去，就可以把两端的元素完成排序，之后处理中间部分，中间部分如果过大就继续递归用这种方式继续分割，如果不大，就用单轴分割
* 对两部分递归调用下去。
*
*/
/* 双轴快排的测试数组
int[] a = new int[300];
for(int i=0;i<30;i++){
a[i]=(int)(Math.random()*300);
}
sort(a);
*/
/* 归并排序算法的测试数组
int[] a = new int[300];
int[] b = new int[10];
for(int i=0;i<30;i++){
a[i]=(int)(Math.random()*300);
for(int j=0;j<10;j++){
a[i*10+j]=a[i]+j+1;
}
}
sort(a);
*/
/**
* 升序排列指定数组.
*
* 这是由Vladimir Yaroslavskiy, Jon Bentley,Joshua Bloch这三个老外写的双
* 轴快速排序算法实现的. 这种算法在处理某些数据集（比如某些会导致其他快排算法性能退化到n方）依旧保持了O(n log(n))
* 的性能,而且他尤其比传统的单轴快排要快
*
* @param a the array to be sorted
*/
public static void sort(int[] a) {
DualPivotQuicksort.sort(a);/*调用双轴快排方法*/
}
/*
* 符合类型的数组排序
*/
/**
* 后面的代码基本都过时了，就不贴了，直接进正题看看排序的算法
*/
final class DualPivotQuicksort {
private DualPivotQuicksort() {}
/**
* 这个指数组部分有序的值，也就是说，当数组本来是升序突然变成了降序或者等序，count值就+1,67指这种顺序的变化次数不
* 高于67次，也就是总体无序，部分有序的数组。
*/
private static final int MAX_RUN_COUNT = 67;
/**
* 使用归并排序相同元素的最大数目，如果相同元素多于这个数，那么还是用快排去排
*/
private static final int MAX_RUN_LENGTH = 33;
/**
* 如果被排序数组的个数少于这个常量，就直接用快排的方法去排序
*/
private static final int QUICKSORT_THRESHOLD = 286;
/**
* 如果被排序数组的个数少于47，就直接用插入排序排
*/
private static final int INSERTION_SORT_THRESHOLD = 47;
/*
* 一些重载的方法
*/
public static void sort(int[] a) {
sort(a, 0, a.length - 1);
}
public static void sort(int[] a, int left, int right) {
if (right - left < QUICKSORT_THRESHOLD) /*长度小于快排的那个值就用快排，不小于就继续往下走，数值为286*/
sort(a, left, right, true);
return;
}
/*检查一下这个数组是不是基本有序，运行机制是，用run来数组来顺序的变化的点（比如正序变为逆序或等序，或者相反），
count来记录数组顺序变化的次数，如果次数小说明数组高度有序，然后用下面的归并排序来排，如果数字大说明数组高度无序
就跳到双轴快排来排序*/
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]) { // 升序序列数
while (++k <= right && a[k - 1] <= a[k]);
} else if (a[k] > a[k + 1]) { // 降序虚列数
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;
}
}
// 检查一下特殊情况
if (run[count] == right++) { // The last run contains one element
run[++count] = right;
} else if (count == 1) { // The array is already sorted
return;
}
/*
* 只有当数组很大（大于286），而且部分高度有序的时候，用下面的归并排序排。
* 下面声明一个数组，归并需要用到额外的数组*/
int[] b; byte odd = 0;
for (int n = 1; (n <<= 1) < count; odd ^= 1);
if (odd == 0) {
b = a; a = new int[b.length];
for (int i = left - 1; ++i < right; a[i] = b[i]);
} else {
b = new int[a.length];
}
/* 归并排序部分,这个地方就需要用到，前面用到的判断是否部分高度有序的run数组和conut值，run数组代表部分有序的起止坐标，count代表无序的子序列数，
* 而且这部分归并用三层循环实现，并没有用到递归，开销要比递归小很多*/
/* 思路是从run数组中取三个值，第一个值和第二个值为第一个有序子序列起始地址，第二个和第三个为第二个有序子序列，然后对这两个子序列比较排序放到数组b中，
* 这两个有序子序列就合并为一个有序子序列，更新run数组和count的值，然后继续往后取两个子序列，继续归并，直到完成此次遍历，然后根据新的run和count进
* 行下一次归并，直到count值小于等于1，表明数组已经排序完毕*/
for (int last; count > 1; count = last) {
for (int k = (last = 0) + 2; k <= count; k += 2) {
int hi = run[k], mi = run[k - 1];
for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
if (q >= hi || p < mi && a[p] <= a[q]) {
b[i] = a[p++];
} else {
b[i] = a[q++];
}
}
run[++last] = hi;
}
/*count的值不为偶数时，那么最后一个有序子序列肯定没参与到归并里的，将没参与归并的数组完全复制到b中，参与下一轮的归并*/
if ((count & 1) != 0) {
for (int i = right, lo = run[count - 1]; --i >= lo;
b[i] = a[i]
);
run[++last] = right;
}
int[] t = a; a = b; b = t;
}
}
private static void sort(int[] a, int left, int right, boolean leftmost) {
int length = right - left + 1;
if (length < INSERTION_SORT_THRESHOLD) {/*数组特别小的就用插入排序，数值为47*/
if (leftmost) {
/*
* 所有的分割小块中最左边的一块用传统的插入排序来排序，只有1块，其余所有用下面的pair insertion
* sort来排序
*/
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 {
/*
* 跳过有序的序列
*/
do {
if (left >= right) {
return;
}
} while (a[++left] >= a[left - 1]);
/*
* 每个边界元素作为哨兵, 这样每次迭代可以让我们避免左侧的检查. 此外，我们用效率更高的算法, 也就是所谓的pair insertion
* sort, 比传统的插入排序更快（PS：确实效率更高，比传统的要少很多不必要的比较）。
*/
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;
}
// 因为值近似的等于长度除以7，就取名seventh。可以的，这个起名给满分
int seventh = (length >> 3) + (length >> 6) + 1;
/*
* 对5个等间距的数组中心元素排序. 这些元素将作为下面描述的支点。
* 根据经验，这种选择的方法会在处理大范围输入的时候更有效率
*/
int e3 = (left + right) >>> 1; // 中指针
int e2 = e3 - seventh;
int e1 = e2 - seventh;
int e4 = e3 + seventh;
int e5 = e4 + seventh;
/*对这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; }
}
}
}
// 指针们
int less = left; // 中心部分的起始下标
int great = right; // 右边部分的起始下标（这两个概念对照下面的那个图看会好理解）
if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
/*
* 用5个元素中2,4个元素取出来作为指针，要注意的是 pivot1要小于pivot2.
*/
int pivot1 = a[e2];
int pivot2 = a[e4];
/*
* 第一个和最后一个元素来填两个指针挪出来的坑，分割完毕后，两个指针归为，这就是他们俩的最终位置，而且不会再变也不用参加接下来的排序了
*/
a[e2] = a[left];
a[e4] = a[right];
/*
* 跳过左边比pivot1小的元素和右边比pivot大的元素，也就是这些元素不用动了，放在原地就好
*/
while (a[++less] < pivot1);
while (a[--great] > pivot2);
/*
* 分割:也就是小于pivot1的都放到左边去，大于pivot2的都放到右边去，用less和great来记录两边的元素的分界下标
*
* 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];
/*
* 这里用 "a[i] = b; i++;" 而不是
* "a[i++] = b;" 是性能问题，也就是这么写运行快一点.
*/
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];
}
/*
* 这里用 "a[i] = b; i--;" 而不是
* "a[i--] = b;" 因为性能问题.
*/
a[great] = ak;
--great;
}
}
// 把指针放在他们的最终位置
a[left] = a[less - 1]; a[less - 1] = pivot1;
a[right] = a[great + 1]; a[great + 1] = pivot2;
// 然后递归的对左边部分和右边部分排序，已经归位的指针就不用加进去了
sort(a, left, less - 2, leftmost);
sort(a, great + 2, right, false);
/*
* 上边的递归完事，左边的和右边就已经排完了，而且都在在自己该在的位置，接下来就是中间的部分，
* 下面判断中间部分范围大小，如果大于七分之四（e1和e5的作用在这才看出来），就把所有和指针相等的元素也扔过去
* 然后对这一部分递归，算法和上边一模一样，没啥区别，只是<>改成了=
*/
if (less < e1 && e5 < great) {
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];
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);
} else {
/*
* 如果不算很大，就以中间那个数也就是e3位povit，用一样的算法来排
*/
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[k] = pivot;
}
a[great] = ak;
--great;
}
}
sort(a, left, less - 1, leftmost);
sort(a, great + 1, right, false);
}
}
/**
* Sorts the specified array.
*
* @param a the array to be sorted
*/