排序算法——随机快速排序

た入场券 2023-01-16 12:27 117阅读 0赞

# 引言 #

随机快排是一个非常有意思的排序排序算法，它的算法思想用到了如递归、荷兰国旗问题等诸多元素，还意外的引入了随机性的概念。

以下将逐步总结三个版本的快速排序，由浅入深总结快速排序的经典实现过程。

荷兰国旗问题参考：《[荷兰国旗问题][Link 1]》

# 一、快速排序1.0 #

在荷兰国旗问题中，我们通过简单的逻辑可以将一个数组分为两个区域或三个区域，但往往需要在题目之初给定一个 target 作为目标数以此划分。

而在快速排序算法中，这个 target 选为排序范围上的最右边的数——arr\[R\]，我们以 R 上的数为 target 将R位置左侧先划分为两块区域 小于等于区和大于区，最后再将 R 与 大于区域的第一个数交换就可以完成整体的划分。

通过上面的这个主过程，我们通过递归，将左右两部分递归完成上面的过程，最终就可以实现整个数组的有序。

> **注意**，在具体编码时，由于递归每次都需要选出一个数作为基准数，依此划分两块区域，在这个版本中，我们以 R 位置上的数为基准数，以此来划分，循环完毕后，我们只实现了R位置左侧的内容变为小于等于区和大于区，这时必须在循环外部额外单独处理一次基准数，做法就是将它与小于等于区的右边+1位置交换，并将小于等于区扩大一个位置即可。

private static int partition(int[] arr, int L, int R) {
            if (L > R)
                return -1;
            if (L == R)
                return L;
            int lessEqual = L - 1;
            int cur = L;
            while (cur < R) {
                if (arr[cur] <= arr[R])
                    SortUtil.swap(arr, ++lessEqual, cur);
                // 这里必须写在 if 外面自加，如果写在传参处自加，会导致大于时无法自加
                cur++;
            }
            SortUtil.swap(arr, ++lessEqual, R);
            return lessEqual;
        }

最后通过递归完成划分区域的步骤：

public static void quickSort1(int[] arr) {
            // 注意不要写成 lenth == 0
            if (arr == null || arr.length < 2)
                return;
            process1(arr, 0, arr.length - 1);
        }
    
        private static void process1(int[] arr, int L, int R) {
            if (L >= R)
                return;
            int M = partition(arr, L, R);
            process1(arr, L, M - 1);
            process1(arr, M + 1, R);
        }

说明一下 M，它代表一个\[L, R\]范围上的 中点位置，取自 partition 方法的返回值。partition 方法将 L R 范围上的数组划分成两个区域——小于等于区和大于区，M 即为上一次分区划分的基准数。

就1.0版本的快排而言，由于每次基准数都取自 R 位置上的数，那么思考这样一个问题，最理想的基准数和最差基准数分别是怎样的情况呢？

如果可以将 \[L, R\] 范围上的数充分等分，那么这就是最理想的基准数，如果范围上的数都偏向基准数一侧，那么就可能使算法花费更长的执行时间。

# 二、快速排序2.0 #

在1.0 中，我们选取基准数将\[L, R\]范围上的数划分为两部分，但是对于基准数重复的情况，它可能会造成在小于等于区不连续的情况，导致可能需要重复选择相同基准数的问题。

对于这个问题，通过荷兰国旗问题（三块分）的方法可以很好的优化。

/** 快排2.0*/
        public static void quickSort2(int[] arr) {
            if (arr == null || arr.length < 2)
                return;
            process2(arr, 0, arr.length - 1);
        }
    
        /** 迭代处理*/
        private static void process2(int[] arr, int L, int R) {
            if (L >= R)
                return;
            int[] midRange = Code2_NetherlandsFlag.netherlandsFlag(arr, L, R, arr[R]);
            process2(arr, L, midRange[0] - 1);
            process2(arr, midRange[1] + 1, R);
        }
    
        /*** 荷兰国旗划分*/
        public static int[] netherlandsFlag(int[] arr, int L, int R, int target) {
            if (L > R)
                return new int[]{-1, -1};
            if (L == R)
                return new int[]{L, R};
            int less = L - 1;
            int more = R + 1;
            int curr = L;
            while (curr < more) {
                if (arr[curr] == target) {
                    curr++;
                } else if (arr[curr] < target) {
                    SortUtil.swap(arr, curr, less + 1);
                    less++;
                    curr++;
                } else {
                    SortUtil.swap(arr, curr, more - 1);
                    more--;
                }
            }
            // 等于区域的左边界和右边界 [less + 1, more - 1]
            return new int[]{less + 1, more - 1};
        }

# 三、快速排序 3.0 —— 随机快速排序 #

在1.0的版本中提到，当 R 位置选取的基准数可以比较好的中分数组元素，那么递归函数处理两侧的时间就会大致均分，从而可以达到 O(N \* logN) 时间复杂度，而为了更好的达到这一点，在 2.0 基础之上，我们需要随机选取数组上的一个元素，将其视为基准数，然后其他的内容基本和 2.0 没有任何区别。

注意，在随机快排的递归进行前选取基准数的时候，我们依然选取 R 位置上的数，只不过我们会先随机一个位置，将其换到 R 位置上，在进行递归处理：

完整代码如下：

/** 快排3.0*/
        public static void quickSort3(int[] arr) {
            if (arr == null || arr.length < 2)
                return;
            process3(arr, 0, arr.length - 1);
        }
    
        private static void process3(int[] arr, int L, int R) {
            if (L >= R)
                return;
            // 随机选取1个位置上的数换到 R 位置上
            SortUtil.swap(arr, L + (int) Math.random() * (R - L + 1), R);
            int[] midRange = Code2_NetherlandsFlag.netherlandsFlag(arr, L, R, arr[R]);
            process2(arr, L, midRange[0] - 1);
            process2(arr, midRange[1] + 1, R);
        }
    
        public static int[] netherlandsFlag(int[] arr, int L, int R, int target) {
            if (L > R)
                return new int[]{-1, -1};
            if (L == R)
                return new int[]{L, R};
            int less = L - 1;
            int more = R + 1;
            int curr = L;
            while (curr < more) {
                if (arr[curr] == target) {
                    curr++;
                } else if (arr[curr] < target) {
                    SortUtil.swap(arr, curr, less + 1);
                    less++;
                    curr++;
                } else {
                    SortUtil.swap(arr, curr, more - 1);
                    more--;
                }
            }
            // 等于区域的左边界和右边界 [less + 1, more - 1]
            return new int[]{less + 1, more - 1};
        }

# 四、随机快排的时间复杂度 #

在每次随机选取基准数时，每个数的选中概率是 1/N ，根据数学家的证明，随机快排的时间复杂度会收敛于 O(N \* logN)，它并不代表不会出现 O(N ^ 2) 的情况，而是将最坏的情况变成了随机概率事件。

# 总结 #

快速排序借助了几个非常重要的算法技巧：迭代、荷兰国旗问题、随机概率性。

它的时间复杂度会收敛于 O(N \* logN)。

[Link 1]: https://morty.blog.csdn.net/article/details/116081760