int[]排序

  • 长度大于QUICKSORT_THRESHOLD(286)时，调用sort方法
    • 长度大于INSERTION_SORT_THRESHOLD时，采用快排
      • 优化：对Pivot的选取。通过位运算，获取长度1/7近似值。以长度中点、中点左右1/7、2/7共5个值作为Pivot
    • 小于的，使用插入排序
  • 否则，判断是否高度结构化(即，是否已经接近排序完成
    • 定义一个常量MAX_RUN_COUNT = 67;
    • 定义一个计数器int count = 0; 定义一个数组int[] run 使之长度为MAX_RUN_COUNT + 1;
    • 令run[0] = left, 然后从传入数组的最左侧left开始遍历,
      • 若数组的前n个元素均为升序/降序排列, 而第n + 1个元素的升/降序发生了改变, 则++count，并将第n个元素的索引存入run[conut]
      • 若数组中连续相等的元素长度超过MAX_RUN_LENGTH(33)，就调用快排
      • 在遍历过程中，将降序的序列进行翻转变为升序
    • 如果conut<MAX_RUN_COUNT,即升序降序改变次数小于67次，就认为是高度结构化的
  • 高度结构化的，如果还未排好序，使用归并排序
  • 未高度结构化的，使用快排

image.png

快排

image.png

  2. //选取Pivot：通过位运算获取数组长度的1/7的近似值(位运算无法精确表示1/7)
  3. int seventh = (length >> 3) + (length >> 6) + 1;
  5. //获取数组中间位置左右1/7、2/7处的索引(e1、e2、e4、e5)
  6. int e3 = (left + right) >>> 1; 
  7. int e2 = e3 - seventh;
  8. int e1 = e2 - seventh;
  9. int e4 = e3 + seventh;
  10. int e5 = e4 + seventh;
  12. //对e1-e5进行插入排序
  13. if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
  15.         if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
  16.             if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  17.         }
  18.         if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
  19.             if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  20.                 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  21.             }
  22.         }
  23.         if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
  24.             if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
  25.                 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  26.                     if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  27.                 }
  28.             }
  29.         }
  31. int less  = left;  
  32. int great = right; 
  34. //5个元素没有相同的，就以e2、e4作为双枢轴
  35. if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
  37.             int pivot1 = a[e2];
  38.             int pivot2 = a[e4];
  41.             a[e2] = a[left];
  42.             a[e4] = a[right];
  44.            //使得less左边元素都小于pivot1，great元素右边都小于povot2
  45.             while (a[++less] < pivot1);
  46.             while (a[--great] > pivot2);
  48.     //开始排序，对less和great之间的元素排序，达到下图的效果
  49.             /*
  50.              * Partitioning:
  51.              *
  52.              *   left part           center part                   right part
  53.              * +--------------------------------------------------------------+
  54.              * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
  55.              * +--------------------------------------------------------------+
  56.              *               ^                          ^       ^
  57.              *               |                          |       |
  58.              *              less                        k     great
  59.              *
  60.              * Invariants:
  61.              *
  62.              *              all in (left, less)   < pivot1
  63.              *    pivot1 <= all in [less, k)     <= pivot2
  64.              *              all in (great, right) > pivot2
  65.              *
  66.              * Pointer k is the first index of ?-part.
  67.              */
  68.             outer:
  69.             for (int k = less - 1; ++k <= great; ) {
  70.                 int ak = a[k];
  71.                 if (ak < pivot1) {
  72.                     //ak跟a[less]交换
  73.                     a[k] = a[less];
  74.                     a[less] = ak;
  75.                     ++less;
  76.                 } else if (ak > pivot2) {
  77.                     //如果great大于pivot2，great继续往左边移动
  78.                     while (a[great] > pivot2) {
  79.                         if (great-- == k) {
  80.                             break outer;
  81.                         }
  82.                     }
  83.                     if (a[great] < pivot1) { 
  84.                         //great小于pivot1，将great移到less的位置
  85.                         a[k] = a[less];
  86.                         a[less] = a[great];
  87.                         ++less;
  88.                     } else { 
  89.                         // pivot1 <= a[great] <= pivot2，将great赋值到k的位置
  90.                         a[k] = a[great];
  91.                     }
  92.                     //ak跟a[great]交换
  93.                     a[great] = ak;
  94.                     --great;
  95.                 }
  96.             }
  98.             // 定位pivot1和pivot2的位置
  99.             a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
  100.             a[right] = a[great + 1]; a[great + 1] = pivot2;
  102.             // Sort left and right parts recursively, excluding known pivots
  103.             sort(a, left, less - 2, leftmost);
  104.             sort(a, great + 2, right, false);
  106.             /*
  107.              * If center part is too large (comprises > 4/7 of the array),
  108.              * swap internal pivot values to ends.
  109.              */
  110.             if (less < e1 && e5 < great) {
  111.                 /*
  112.                  * Skip elements, which are equal to pivot values.
  113.                  */
  114.                 while (a[less] == pivot1) {
  115.                     ++less;
  116.                 }
  118.                 while (a[great] == pivot2) {
  119.                     --great;
  120.                 }
  122.                 /*
  123.                  * Partitioning:
  124.                  *
  125.                  *   left part         center part                  right part
  126.                  * +----------------------------------------------------------+
  127.                  * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
  128.                  * +----------------------------------------------------------+
  129.                  *              ^                        ^       ^
  130.                  *              |                        |       |
  131.                  *             less                      k     great
  132.                  *
  133.                  * Invariants:
  134.                  *
  135.                  *              all in (*,  less) == pivot1
  136.                  *     pivot1 < all in [less,  k)  < pivot2
  137.                  *              all in (great, *) == pivot2
  138.                  *
  139.                  * Pointer k is the first index of ?-part.
  140.                  */
  141.                 outer:
  142.                 for (int k = less - 1; ++k <= great; ) {
  143.                     int ak = a[k];
  144.                     if (ak == pivot1) { // Move a[k] to left part
  145.                         a[k] = a[less];
  146.                         a[less] = ak;
  147.                         ++less;
  148.                     } else if (ak == pivot2) { // Move a[k] to right part
  149.                         while (a[great] == pivot2) {
  150.                             if (great-- == k) {
  151.                                 break outer;
  152.                             }
  153.                         }
  154.                         if (a[great] == pivot1) { // a[great] < pivot2
  155.                             a[k] = a[less];
  156.                             /*
  157.                              * Even though a[great] equals to pivot1, the
  158.                              * assignment a[less] = pivot1 may be incorrect,
  159.                              * if a[great] and pivot1 are floating-point zeros
  160.                              * of different signs. Therefore in float and
  161.                              * double sorting methods we have to use more
  162.                              * accurate assignment a[less] = a[great].
  163.                              */
  164.                             a[less] = pivot1;
  165.                             ++less;
  166.                         } else { // pivot1 < a[great] < pivot2
  167.                             a[k] = a[great];
  168.                         }
  169.                         a[great] = ak;
  170.                         --great;
  171.                     }
  172.                 }
  173.             }
  175.             // Sort center part recursively
  176.             sort(a, less, great, false);
  178.         } else { // Partitioning with one pivot
  179.             //存在相同元素，就使用e3作为枢轴
  180.             int pivot = a[e3];
  182.             /*
  183.              * Partitioning degenerates to the traditional 3-way
  184.              * (or "Dutch National Flag") schema:
  185.              *
  186.              *   left part    center part              right part
  187.              * +-------------------------------------------------+
  188.              * |  < pivot  |   == pivot   |     ?    |  > pivot  |
  189.              * +-------------------------------------------------+
  190.              *              ^              ^        ^
  191.              *              |              |        |
  192.              *             less            k      great
  193.              *
  194.              * Invariants:
  195.              *
  196.              *   all in (left, less)   < pivot
  197.              *   all in [less, k)     == pivot
  198.              *   all in (great, right) > pivot
  199.              *
  200.              * Pointer k is the first index of ?-part.
  201.              */
  202.             for (int k = less; k <= great; ++k) {
  203.                 if (a[k] == pivot) {
  204.                     continue;
  205.                 }
  206.                 int ak = a[k];
  207.                 //小于pivot，直接将k与less交换
  208.                 if (ak < pivot) { 
  209.                     a[k] = a[less];
  210.                     a[less] = ak;
  211.                     ++less;
  212.                 } else { 
  213.                     //开始反向从great遍历，如果great元素>枢轴，无需交换，great向前移动
  214.                     while (a[great] > pivot) {
  215.                         --great;
  216.                     }
  217.                     //great元素小于pviot，就跟先将less复制到k指向的位置(此时k位置原本的元素由ak保存)，然后将great元素复制到less，less++
  218.                     //即，less-->k， great-->less交换，k -->great
  219.                     if (a[great] < pivot) { // a[great] <= pivot
  220.                         a[k] = a[less];
  221.                         a[less] = a[great];
  222.                         ++less;
  223.                     } else { 
  224.                         //如果great等于pivot，将pivot的值直接复制到k指向的位置
  225.                         a[k] = pivot;
  226.                     }
  227.                     //将k的元素复制到great
  228.                     a[great] = ak;
  229.                     --great;
  230.                 }
  231.             }
  233.             /*
  234.              * Sort left and right parts recursively.
  235.              * All elements from center part are equal
  236.              * and, therefore, already sorted.
  237.              */
  238.             sort(a, left, less - 1, leftmost);
  239.             sort(a, great + 1, right, false);
  240.         }

高度结构化判断

  1. // Check if the array is nearly sorted
  2.         //    k的值表示多个升序序列尾部索引，count表示升降序改变次数
  3.         for (int k = left; k < right; run[count] = k) {
  4.             if (a[k] < a[k + 1]) { 
  5.                 //升序
  6.                 while (++k <= right && a[k - 1] <= a[k]);
  7.             } else if (a[k] > a[k + 1]) { 
  8.                 //降序
  9.                 while (++k <= right && a[k - 1] >= a[k]);
  10.                 //翻转序列，将降序变为升序
  11.                 for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
  12.                     int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
  13.                 }
  14.             } else { 
  15.                 //相同元素超过33，使用快排
  16.                 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
  17.                     if (--m == 0) {
  18.                         sort(a, left, right, true);
  19.                         return;
  20.                     }
  21.                 }
  22.             }
  24.             //当遍历过程中发现变化次数高于33次时，直接使用快排
  25.             if (++count == MAX_RUN_COUNT) {
  26.                 sort(a, left, right, true);
  27.                 return;
  28.             }
  29.         }

T[]排序

参见容器排序：https://www.yuque.com/zhicizhongnian/nr4160/huyv1h