让面试官满意的排序算法（图文解析）

重头戏：双支点快排！

快排虽然稳定性不如归并排序，但是它不用复制来复制去，省去了一段数组的空间，在数组元素较少的情况下稳定性影响也会下降（>插排阈值 ，<快排阈值），优先使用快排

双支点快排在原有的快排基础上，多加一个支点，左右共进，效率提升

看图：

1. 第一步，取支点

   注意：如果5个节点有相等的任两个节点，说明数据不够均匀，那就要使用单节点快排

2. 快排

源码（int为例，这么长估计也没人看）

// Inexpensive approximation of length / 7 
// 快排阈值是286 其7分之一小于等于1/8+1/64+1
int seventh = (length >> 3) + (length >> 6) + 1;

// 获取分成7份的五个中间点
int e3 = (left + right) >>> 1; // The midpoint
int e2 = e3 - seventh;
int e1 = e2 - seventh;
int e4 = e3 + seventh;
int e5 = e4 + seventh;

// 保证中间点的元素从小到大排序
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; }
}
     }
}

// Pointers
int less  = left;  // The index of the first element of center part
int great = right; // The index before the first element of right part

//点彼此不相等——分三段快排，否则分两段
if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
    
    int pivot1 = a[e2];
    int pivot2 = a[e4];

    
    a[e2] = a[left];
    a[e4] = a[right];

    while (a[++less] < pivot1);
    while (a[--great] > 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];
     
     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[great] = ak;
     --great;
 }
    }

    // Swap pivots into their final positions
    a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
    a[right] = a[great + 1]; a[great + 1] = pivot2;

    // Sort left and right parts recursively, excluding known pivots
    sort(a, left, less - 2, leftmost);
    sort(a, great + 2, right, false);

    
    if (less < e1 && e5 < great) {
 
 while (a[less] == pivot1) {
     ++less;
 }

 while (a[great] == pivot2) {
     --great;
 }

 
 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 { // Partitioning with one pivot
    
    int pivot = a[e3];

    
    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[great] == pivot
  
  a[k] = pivot;
     }
     a[great] = ak;
     --great;
 }
    }

    
    sort(a, left, less - 1, leftmost);
    sort(a, great + 1, right, false);
}

//判断结构是否适合归并排序
int[] run = new int[MAX_RUN_COUNT + 1];
int count = 0; run[0] = left;

// Check if the array is nearly sorted
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 { 
 //连续MAX_RUN_LENGTH（33）个相等元素，使用快排
 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
     if (--m == 0) {
  sort(a, left, right, true);
  return;
     }
 }
    }

    //count达到MAX_RUN_LENGTH，使用快排
    if (++count == MAX_RUN_COUNT) {
 sort(a, left, right, true);
 return;
    }
}

// Check special cases
// Implementation note: variable "right" is increased by 1.
if (run[count] == right++) { // The last run contains one element
    run[++count] = right;
} else if (count == 1) { // The array is already sorted
    return;
}

byte odd = 0;
for (int n = 1; (n <<= 1) < count; odd ^= 1);

// Use or create temporary array b for merging
int[] b;   // temp array; alternates with a
int ao, bo;// array offsets from 'left'
int blen = right - left; // space needed for b
if (work == null || workLen < blen || workbase + blen > work.length) {
    work = new int[blen];
    workbase = 0;
}
if (odd == 0) {
    System.arraycopy(a, left, work, workbase, blen);
    b = a;
    bo = 0;
    a = work;
    ao = workbase - left;
} else {
    b = work;
    ao = 0;
    bo = workbase - left;
}

// Merging
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 + ao] <= a[q + ao]) {
  b[i + bo] = a[p++ + ao];
     } else {
  b[i + bo] = a[q++ + ao];
     }
 }
 run[++last] = hi;
    }
    if ((count & 1) != 0) {
 for (int i = right, lo = run[count - 1]; --i >= lo;
      b[i + bo] = a[i + ao]
     );
 run[++last] = right;
    }
    int[] t = a; a = b; b = t;
    int o = ao; ao = bo; bo = o;
}