CS4L28——快速排序

快速排序

快速排序（quick sort）是一种基于分治策略的排序算法，运行高效，应用广泛。

快速排序基本原理

简略来说：选取基准，产生左右标识，左右比基准，满足则换位，排完一次，基准定位，左右递归，直到有序

详细解释：快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。

  1. 选取数组最左端元素作为基准数，初始化两个指针 i​ 和 j 分别指向数组的两端。
  2. 设置一个循环，在每轮中使用 i​（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素。
  3. 循环执行步骤 2.​ ，直到 i​ 和 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
static void QuickSort(int[] nums, int left, int right)
{
    // 第七步：递归函数结束条件，当传入的左边界和右边界不重叠时就说明需要进行排序
    if (left >= right)
        return;
    // 第一步：声明基准值，左游标和右游标并初始化，基准值选取最左侧元素
    int temp, tempLeft, tempRight;
    temp = nums[left];
    tempLeft = left;
    tempRight = right;
    // 第二步：核心交换逻辑（哨兵划分逻辑），左右游标会不停变化，要左右游标不相同时才会继续变化
    while (tempLeft != tempRight)
    {
        // 第四步：比较位置交换，首先从右边比较，看值是否有资格放到基准值的右侧（即大于基准值）
        while (tempLeft < tempRight && nums[tempRight] > temp)
        {
            tempRight--;
        }
        // 若发现有值小于基准值，则没有资格在基准值的右侧，则移动结束，证明可以交换位置
        nums[tempLeft] = nums[tempRight];
        // 接下来移动左侧游标，从左侧比较，看值是否有资格放到基准值的左侧（即小于基准值）
        while (tempLeft < tempRight && nums[tempLeft] < temp)
        {
            tempLeft++;
        }
        // 若发现有值大于基准值，则没有资格在基准值的左侧，移动结束，证明可以交换位置
        nums[tempRight] = nums[tempLeft];
    }
    // 第五步：放置基准值，跳出循环后，将基准值放在中间位置（即tempRight和tempLeft相遇的位置）
    nums[tempRight] = temp;
    // 第六步：递归基准值左右两侧的子数组
    QuickSort(nums, left, tempRight - 1);
    QuickSort(nums, tempLeft + 1, right);
}

static void Main(string[] args)
{
    int[] arr = new int[] { 8, 7, 1, 5, 4, 2, 6, 3, 9 };
    Console.Write("未排序：");
    for (int i = 0; i < arr.Length; i++)
    {
        Console.Write($"{arr[i]}, ");
    }
    Console.Write("\n");
    QuickSort(arr, 0, arr.Length - 1);
    Console.Write("已排序：");
    for (int i = 0; i < arr.Length; i++)
    {
        Console.Write($"{arr[i]}, ");
    }
    Console.Write("\n");
}

输出：

1
2
未排序：8, 7, 1, 5, 4, 2, 6, 3, 9, 
已排序：1, 2, 3, 4, 5, 6, 7, 8, 9,

归并排序和快速排序都会用到递归，两者的区别：

  • 相同点：

    1. 他们都会用到递归
    2. 都会把数组分成几部分

  • 不同点：

    1. 归并排序递归过程中会不停产生新数组用于合并；快速排序不会产生新数组
    2. 归并排序是拆分数组完毕后再进行排序；快速排序是边排序边拆分

套路写法：

  • 基准值变量，左右游标记录
  • 3 层 while 循环，游标不停左右移动，重合则结束，结束定基准
  • 递归排左右，错位则结束

算法特性

  • 时间复杂度为 **O(nlog⁡⁡n)O(n\log⁡n)**​ 、非自适应排序：在平均情况下，哨兵划分的递归层数为 log⁡⁡n\log⁡n ，每层中的总循环数为 nn ，总体使用 O(nlog⁡⁡n)O(n\log⁡n) 时间。
    在最差情况下，每轮哨兵划分操作都将长度为 nn 的数组划分为长度为 00 和 n−1n−1 的两个子数组，此时递归层数达到 nn ，每层中的循环数为 nn ，总体使用 O(n2)O(n^2) 时间。
  • 空间复杂度为 **O(n)O(n)**​ 、原地排序：在输入数组完全倒序的情况下，达到最差递归深度 nn ，使用 O(n)O(n) 栈帧空间。排序操作是在原数组上进行的，未借助额外数组。
  • 非稳定排序：在哨兵划分的最后一步，基准数可能会被交换至相等元素的右侧。

快速排序为什么快

从名称上就能看出，快速排序在效率方面应该具有一定的优势。尽管快速排序的平均时间复杂度与“归并排序”和“堆排序”相同，但通常快速排序的效率更高，主要有以下原因。

  • 出现最差情况的概率很低：虽然快速排序的最差时间复杂度为 O(n2)O(n^2) ，没有归并排序稳定，但在绝大多数情况下，快速排序能在 O(nlog⁡⁡n)O(n\log⁡n) 的时间复杂度下运行。
  • 缓存使用效率高：在执行哨兵划分操作时，系统可将整个子数组加载到缓存，因此访问元素的效率较高。而像“堆排序”这类算法需要跳跃式访问元素，从而缺乏这一特性。
  • 复杂度的常数系数小：在上述三种算法中，快速排序的比较、赋值、交换等操作的总数量最少。这与“插入排序”比“冒泡排序”更快的原因类似。

基准值优化

快速排序在某些输入下的时间效率可能降低。
举一个极端例子，假设输入数组是完全倒序的，由于我们选择最左端元素作为基准数，那么在哨兵划分完成后，基准数被交换至数组最右端，导致左子数组长度为 n−1n−1、右子数组长度为 00 。如此递归下去，每轮哨兵划分后都有一个子数组的长度为 00 ，分治策略失效，快速排序退化为“冒泡排序”的近似形式。

为了尽量避免这种情况发生，我们可以优化哨兵划分中的基准数的选取策略。
例如，我们可以随机选取一个元素作为基准数。然而，如果运气不佳，每次都选到不理想的基准数，效率仍然不尽如人意。

需要注意的是，编程语言通常生成的是“伪随机数”。如果我们针对伪随机数序列构建一个特定的测试样例，那么快速排序的效率仍然可能劣化。

为了进一步改进，我们可以在数组中选取三个候选元素（通常为数组的首、尾、中点元素），并将这三个候选元素的中位数作为基准数。
这样一来，基准数“既不太小也不太大”的概率将大幅提升。当然，我们还可以选取更多候选元素，以进一步提高算法的稳健性。
采用这种方法后，时间复杂度劣化至 O(n2)O(n^2) 的概率大大降低。

1
2
3
4
5
6
7
8
9
10
11
```

## 尾递归优化

**在某些输入下，快速排序可能占用空间较多**。  
以完全有序的输入数组为例，设递归中的子数组长度为 $m$ ，每轮哨兵划分操作都将产生长度为 $0$ 的左子数组和长度为 $m−1$ 的右子数组，  
这意味着每一层递归调用减少的问题规模非常小（只减少一个元素），递归树的高度会达到 $n−1$ ，此时需要占用 $O(n)$ 大小的栈帧空间。

为了防止栈帧空间的累积，我们可以在每轮哨兵排序完成后，比较两个子数组的长度，**仅对较短的子数组进行递归**。  
由于较短子数组的长度不会超过 $n/2$ ，因此这种方法能确保递归深度不超过 $\log⁡n$，从而将最差空间复杂度优化至 $O(\log⁡n)$。代码如下所示：