双枢轴快速排序与 Arrays.sort()
   点滴记录   0 评论   1324 浏览

双枢轴快速排序与 Arrays.sort()

   点滴记录   0 评论   1324 浏览

时间复杂度差距

当数据量大起来的时候可以看到n*log(n)以及n^2,n^3,2^n的时间复杂度图像都已经快成竖线了。所以在大数据面前你还在写两个for的n平方时间复杂度的暴力解法算法吗?

Arrays.sort()

因为后面的双指针算法可能要先对数据排序,所以我们来研究下这里面有什么新鲜玩意。

第一层

/**
 * 将指定的数组按数字升序排序。
 *
 * 实现说明:排序算法是 Vladimir Yaroslavskiy、Jon Bentley 和
 * Joshua Bloch 的双枢轴快速排序。 该算法在许多数据集上提供 O(n log(n)) 性能,
 * 导致其他快速排序降级为二次性能,并且通常比传统(单轴)快速排序实现更快。
 * 
 * @param a 要排序的数组
 */
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翻译下就好了。
讲的啥嘞,待会再看。

第二层

/**
 * 使用给定的数组对指定的范围进行排序
 * 如果可能的话,工作区数组切片用于合并
 *
 * @param a 要排序的数组
 * @param 将第一个元素(包括第一个元素)的索引留作排序
 * @param 右边是要排序的最后一个元素(包括)的索引
 * @param 工作空间数组(切片)
 * @param 工作数组中可用空间的起点
 * @param workLen工作数组的可用大小
 */
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,则优先使用快速排序而不是归并排序。再进去。

第三层

/**
 * 按双枢轴快速排序对指定范围的数组进行排序。
 *
 * @param a 要排序的数组
 * @param left 要排序的第一个元素(包括第一个元素)的索引
 * @param right 要排序的最后一个元素(包括)的索引
 * @param leftmost 指示该部分是否在范围的最左边
 */
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个和第四个作为枢轴,而普通的快排是一个基准。

/*
 * 使用五个已排序元素中的第二个和第四个作为枢轴。
 * 这些值是阵列的第一和第二第三圈的廉价近似。请注意pivot1 <= pivot2。
 */
int pivot1 = a[e2];
int pivot2 = a[e4];
/*
 * 要排序的第一个和最后一个元素被移动到以前由枢轴占据的位置。
 * 分区完成后,枢轴被交换回其最终位置,并从后续排序中排除。
 */
a[e2] = a[left];
a[e4] = a[right];

因此可以发现两枢轴,就是两个结点,把数据划分成三部分,三部分再分别递归,可参考下图。

/*
 * Partitioning:
 *
 *   left part           center part                   right part
 * +--------------------------------------------------------------+
 * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
 * +--------------------------------------------------------------+
 *               ^                          ^       ^
 *               |                          |       |
 *              less                        k     great
 *
 * 不变性:
 *
 *              all in (left, less)   < pivot1
 *    pivot1 <= all in [less, k)     <= pivot2
 *              all in (great, right) > pivot2
 *
 * Pointer k is the first index of ?-part.
 */

划分成三部分:leftpart:x<p1,centerpart:p1<=x<=p2,rightpart:x>p2
p1<p2,因为上面排过序。

根据图可知less指向 < p1 的下一个位置,great指向 > p2 的前一个位置。k 是遍历的当前位置。
less 到 k -1 之间的数:p1 <= x <= p2,对变量的当前k位置出现下面三种情况:

while (a[great] > pivot2) {
    if (great-- == k) {
        break outer;
    }
}

再判断:A[great] < pivot1,若成立:说明great位置的数应该在< p1 的部分。

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[i] = b; i--;”而不是“a[i--] = b;”由于性能问题。
 */
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] = ak

结束后:形成最上面的形式,三个部分再分别进行递归。

DualQuickSort代码整理:

public 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) ;

        /*
         * 分区:
         *
         *   left part           center part                   right part
         * +--------------------------------------------------------------+
         * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
         * +--------------------------------------------------------------+
         *               ^                          ^       ^
         *               |                          |       |
         *              less                        k     great
         * 不变性:
         *              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 = 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];
                }
                /*
                 * 这里和下面我们使用 “a[i] = b; i--;”而不是“a[i--] = b;”由于性能问题。
                 */
                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");
        }
    }
}

以上是在47-286范围的数组长度时,大于286的,它会进入归并排序(Merge Sort),
但在之前,它有个小动作,检查数组是否接近排序,Check if the array is nearly sorted:

/*
 * 索引 run[i] 是第 i 次运行的开始(升序或降序)。
 */
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;
    }
}

看他数组具不具备结构:实际逻辑是分组排序,每降序为一个组,像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(n*log(n))、O(n^2)。
普通冒泡排序都是O(n^2)。
双枢轴快速排序在许多数据集上提供O(n*log(n))性能,导致其他快速排序降级为二次性能,
并且通常比传统(单枢轴)Quicksort快。

引用

快速排序(java实现)
DualPivotQuicksort两枢轴快速排序
Java的Arrays.sort()方法到底用的什么排序算法

本文由 RawChen 发表, 最后编辑时间为:2021-10-10 16:43
如果你觉得我的文章不错,不妨鼓励我继续写作。

发表评论
选择表情
Top