排序算法在JDK中的应用（二）快速排序

欢迎点击「算法与编程之美」↑关注我们！

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

作者|杨旭

来源|https://blog.csdn.net/Alex_NINE

在分析上述代码时，可以发现程序会在特殊的情况调用sort()方法即改进后得快速排序，接下来就来分析sort()快速排序的代码实现。

  /**

     * Sorts the  specified range of the array by Dual-Pivot Quicksort.

     * 通过双轴快速排序对指定范围内的数据进行排序

     * @param a  the array to be sorted 被排序的数组

     * @param  left the index of the first element, inclusive, to be sorted 需要排序的第一个元素的位置（包括在内）

     * @param  right the index of the last element, inclusive, to be sorted 需要排序的最后一个元素的位置（包括在内）

     * @param  leftmost indicates if this part is the leftmost in the range leftmost表示该部分是否是范围内最左的部分

     */

    private  static void sort(int[] a, int left, int right, boolean leftmost) {

        int  length = right - left + 1;

        // Use  insertion sort on tiny arrays

        //当数组的长度很小时就是用插入排序，INSERTION_SORT_THRESHOLD=47

        if  (length < INSERTION_SORT_THRESHOLD) {

            if  (leftmost) {

                 /*

                  * Traditional (without sentinel) insertion sort, 传统的插入排序，不使用哨兵元素

                  * optimized for server VM, is used in case of 针对最左边的部分的情况进行了服务器虚拟机的优化

                  * the leftmost part.

                  */

                 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 {

                 /*

                  * Skip the longest ascending sequence. 跳过最长的升序情况，提高算法效率

                  */

                 do {

                     if (left >= right) {

                         return;

                     }

                }  while (a[++left] >= a[left - 1]);

                 /*

                  * Every element from adjoining part plays the role   在这种排序方法中相邻的每个元素都起到了哨兵的作用

                  * of sentinel, therefore this allows us to avoid the  这种办法可以避免我们每次迭代时都要进行左范围检查。

                  * left range check on each iteration. Moreover, we use 而且我们还使用了一个效率更好的算法，我们称之为“双插入排序”，

                  * the more optimized algorithm, so called pair insertion 在快速排序的上下文中（即满足进入sort()方法的数组）他比传统的

                  * sort, which is faster (in the context of Quicksort) 插入排序更快

                  * than traditional implementation of insertion sort.

                  */

                 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;

        }

        //从这里开始是对待排序的元素进行分组处理

        //  Inexpensive approximation of length / 7

        // 使用length/7作为近似的加权长度

        int  seventh = (length >> 3) + (length >> 6) + 1;

        /*

         * Sort  five evenly spaced elements around (and including) the 在范围内的中心元素附近找到5个均匀间隔的元素

         * center  element in the range. These elements will be used for 这些元素将用于下面代码中的枢轴选择

         * pivot  selection as described below. The choice for spacing 根据经验，这些元素的间距能够很好的应对和处理各种各样的输入（待排序的数组）

         * these  elements was empirically determined to work well on

         * a wide  variety of inputs.

         */

        int e3 =  (left + right) >>> 1; // The midpoint

        int e2 =  e3 - seventh;

        int e1 = e2 - seventh;

        int e4 =  e3 + seventh;

        int e5 =  e4 + seventh;

        // Sort  these elements using insertion sort 使用插入排序对这些元素进行排序

        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]) {

            /*

             *  Use the second and fourth of the five sorted elements as pivots. 使用五个分位点中的第二个和第四个作为枢轴

             *  These values are inexpensive approximations of the first and 因为有上面的排序 所以在这里pivot1 <= pivot2

             *  second terciles of the array. Note that pivot1 <= pivot2.

             */

            int  pivot1 = a[e2];

            int  pivot2 = a[e4];

            /*

             *  The first and the last elements to be sorted are moved to the 将要排序的第一个和最后一个元素换到枢轴的位置

             *  locations formerly occupied by the pivots. When partitioning 当分区操作完成后，枢轴元素将和这个元素交换回到原来的位置

             * is  complete, the pivots are swapped back into their final 并排除到后续排序之外

             *  positions, and excluded from subsequent sorting.

             */

            a[e2]  = a[left];

            a[e4]  = a[right];

            /*

             *  Skip elements, which are less or greater than pivot values.

             * 筛选那些比枢轴元素更大或者更小的元素 以此来确定less和great的位置

             */

            while  (a[++less] < pivot1);

            while  (a[--great] > pivot2);

            /*

             * Partitioning:

             *

              *   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.

             * 以下的forless-1开始向右遍历至great，把小于pivot1的元素移动到less左边，大于pivot2的元素移动到great右边。       

             */

             //outer标签

            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];

                     /*

                      * Here and below we use "a[i] = b; i++;" instead

                      * of "a[i++] = b;" due to performance issue.

                      * 在这里分开写的原因是因为前者效率更佳

                      * 想要了解的可以看这里的讨论：https://www.oschina.net/question/3037675_2206753

                      */

                    a[less] = ak;

                     ++less;

                }  else if (ak > pivot2) { // Move a[k] to right part

                     while (a[great] > pivot2) {

                         if (great-- == k) {

                            break outer;

                         }

                     }

                    //通过上面已知great