快速排序-排序-数据结构和算法

1 基本算法

​ 快速排序是一种分治的排序算法。它将一个数组分成2个子数组，将两部分独立排序。听起来和归并排序很像，那么有什么不一样呢？

​ 快速排序和归并排序区别：

• 算法：
  • 归并排序：归并排序将数组分成2个子数组分别排序，在将有序的子数组归并使整个数组有序
  • 快速排序： 快速排序是把数组拆分为2个子数组，当2个子数组有序时，整个数组有序。
• 递归：
  • 归并：递归调用发生在处理整个数组之前
  • 快速：递归调用发生在处理整个数组之后

​ 快速排序类Quick整体代码（初级）如下：

package com.gaogzhen.algorithms4.sort;

import edu.princeton.cs.algs4.StdRandom;

/**
 * @author Administrator
 * @version 1.0
 * @description 快速排序
 * @date 2022-09-30 21:42
 */
public class Quick {
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        if (lo <= hi) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    private static int partition(Comparable[] a, int lo, int hi) {
        // TODO
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

​ 简单说明：

• StdRandom类：由算法第4版封装类
• partition方法：为拆分方法，实现在下面。

partition方法关键在于切分，这个过程使得数组满足3个条件：

• 对于某个j，a[j]已经排定
• a[lo]到a[j-1]中的所有元素都不大于a[j]
• a[j+1]到a[hi]中的所有元素都不小于a[j]

算法排序的证明：

因为每次切分总是能排定一个元素，用归纳法不难证明递归能够正确的将数组排序：如果左子数组和右子数组都是有序的，那么由左子数组（数组中的每个元素都不大于切分元素）、切分元素、右子数组（数组中的每个元素都不小于切分元素）组成的结果数组也一定是有序的。

切分方法具体步骤：

1. 随意选取a[lo]为切分元素

2. 从数组左端开始向右扫描直到找到一个大于等于切分元素的值

3. 从数组右端开始向左扫描直到找到一个小于等于切分元素的值

4. 交换步骤2,3找到的2个元素位置

5. 循环执行步骤2~4

6. 当两个指针相遇时，把切分元素和左子数组最右侧的元素交换

代码实现如下：

/**
     * 拆分数组
     * @param a     目标数组
     * @param lo    数组左边界
     * @param hi    数组有边界
     * @return      切分元素索引
     */
    private static int partition(Comparable[] a, int lo, int hi) {
        // 数组切分为a[lo..j-1],a[j],a[j+1..hi]
        int i = lo, j = hi + 1;
        Comparable v = a[lo];
        while (true) {
            // 左指针从左向右扫描，直到找到大于等于a[j]的元素或者数组最右侧
            while (less(a[++i], v)) if (i == hi) break;
            // 右指针从右向左扫描，直到找到小于等于a[j]的元素或者数组最左侧
            while (less(v, a[--j])) if (j == lo) break;
            // 如果左指针大于等于右指针，循环结束
            if (i >= j) break;
            // 交换a[i], a[j]2个元素位置
            exch(a, i, j);
        }
        // 交换切分元素和a[lo]的位置，此时切分元素已排序
        exch(a, lo, j);
        return j;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

完整源代码在下面代码仓库，下面有几个问题来讨论下：

1.1 原地切分

​ 如果使用辅助数组，可以分容易实现切分，但将切分后的数组在复制会原数组开销很大。如果将空数组创建在递归方法中，那开销会更多。

1.2 边界

​ 如果切分元素是数组中最大或者最小的元素，我们要注意指针别越界。partition()方法一般会添加检测，预防越界。其中，判断条件(j==lo)是冗余的，因为切分元素是a[lo],它不可能比自己小。数组右端也是相同情况，他们都可以去掉。

1.3 随机性

​ StdRandom.shuffle(a)，目的就是打乱数组元素。因为算法对所有的子数组一视同仁，所以子数组也是随机的。这对于预测算法的运行时间很重要。保持随机性的另一种方法是在partition()中随机选择一个切分元素。

1.4 终止循环

​ partition()方法中有3个循环，保证循环结束要格外小心。一个常见的错误是没有考虑数组中有包含和切分元素值相同的其他元素。

1.5 切分元素重复

​ 如上面算法所示，左侧扫描最好是在遇到大于等于切分元素时停下，右侧扫描最好是遇到小于等于切分元素时停下。这样可能将一些等值的元素交换，但在某些应用中，可以避免算法的运行时间变为平方级别。

1.6 终止递归

​ 保证递归正确终止，快排中一个很常见的错误不能保证将切分元素放入正确的位置，导致程序陷入无线递归或者得出错误结果。

2 备注

关于快速排序的性能和改进部分，因为涉及本人的一些盲点，暂时封存，等以后在学习，敢兴趣的可自行查阅相关书籍或者视频。

• 参考
  • 书籍：[1][美]Robert Sedgewich,[美]Kevin Wayne著;谢路云译.算法：第4版[M].北京：人民邮电出版社，2012.10
  • 视频：[2]黑马程序员.Java数据结构与java算法[VD/OL].上海：B站,2022
    • 视频地址：https://www.bilibili.com/video/BV1iJ411E7xW

QQ:806797785

仓库地址：https://gitee.com/gaogzhen/algorithm