一、课上练习

编程练习

1. 数组排序：L3121

二、知识总结

✨ 核心思想

快速排序用于对一组线性存储的数据进行排序，是实践中最常用的排序算法之一。

快速排序的核心思想是分治法（Divide and Conquer）。它通过一个称为基准（pivot）的元素来将数组分割（partition）成两个子数组。子数组中比基准小的元素放在一边，比基准大的元素放在另一边。这一过程称为分区操作。然后，递归地在两个子数组上应用同样的方法，直到数组的大小缩减到 1。

✨ 算法原理

快速排序的步骤主要包括：

1. 选择基准：从数组中选择一个元素作为基准点，常见的选择方法有随机选取、选择第一个元素或最后一个元素等。基准的选择会影响算法的性能。
2. 分区操作：将数组重新排列，所有比基准小的元素都移动到基准的左边，所有比基准大的元素都移动到基准的右边。这个过程结束时，基准元素位于其最终位置。
3. 递归排序：对基准左侧和右侧的两个子数组递归地执行上述步骤，直到每个子数组只包含一个元素。

✨ 代码实现

以下是快速排序的完整实现，使用第一个元素作为基准的分区方法：

1#include<iostream>
2#include<algorithm>
3#include<vector>
4#include "stdio.h"
5#include "time.h"
6using namespace std;
7
8int a[10000005] = {0};
9
10// 该函数用于将数组a的一个段[a[left], a[right]]按照基准值base进行划分
11int partition(int a[], int left, int right) {
12    int base = a[left]; // 选择基准值为当前段的第一个元素
13    while (left < right) {
14        // 从右向左扫描，找到第一个小于基准值的元素
15        while (left < right && a[right] >= base) {
16            right--;
17        }
18        a[left] = a[right]; // 将找到的小于基准值的元素移动到左边
19
20        // 从左向右扫描，找到第一个大于等于基准值的元素
21        while (left < right && a[left] < base) {
22            left++;
23        }
24        a[right] = a[left]; // 将找到的大于等于基准值的元素移动到右边
25    }
26    a[left] = base; // 将基准值放到最终的位置
27    return left; // 返回基准值最终的索引
28}
29
30// 快速排序函数，递归地对数组的一段进行排序
31void quick_sort(int a[], int left, int right) {
32    if (left >= right) {
33        return; // 如果当前段的长度为1或为空，则不需要排序
34    }
35    int mid = partition(a, left, right); // 对当前段进行划分，获得基准值的索引
36
37    quick_sort(a, left, mid - 1); // 递归地对基准值左边的子段进行快速排序
38    quick_sort(a, mid + 1, right); // 递归地对基准值右边的子段进行快速排序
39}
40
41int main() {
42        int n = 0;
43        cin >> n;
44        for (int i = 0; i < n; i++) {
45                cin >> a[i];
46        }
47        quick_sort(a, 0, n - 1);
48        for (int i = 0; i < n; i++) {
49                cout << a[i] << ' ';
50        }
51        cout << endl;
52        return 0;
53}

✨ 执行示例

以数组 [6, 3, 8, 1, 5, 2, 7, 4] 为例：

第一轮分区：partition(a, 0, 7)，选择 base = a[0] = 6

分区后：[4, 3, 2, 1, 5, 6, 7, 8]，6 在最终位置（下标5），左边都 <6，右边都 ≥6。

递归排序左半部分 [4, 3, 2, 1, 5]（下标0~4）：

• base=4，分区后得到 [2, 3, 1, 4, 5]
• 再递归 [2, 3, 1]：base=2，分区后 [1, 2, 3]
• 再递归 [1]：基案返回
• 最终左半部分排序完成：[1, 2, 3, 4, 5]

递归排序右半部分 [7, 8]（下标6~7）：

• base=7，分区后 [7, 8]
• 排序完成

最终结果：[1, 2, 3, 4, 5, 6, 7, 8]

✨ 算法评价

时间复杂度

• 最好情况：O(n log n)，当分区操作每次都能将数组分成两个几乎相等的子数组时
• 平均情况：O(n log n)，对于随机排列的数组通常是这样
• 最坏情况：O(n^2)，当数组已经接近排序完成或完全倒序时，每次分区只能减少一个元素

空间复杂度

快速排序的空间复杂度依赖于递归的深度，可以通过在代码中递归较短的子数组来优化：

• 最好情况：O(log n)，平衡分区
• 最坏情况：O(n)，不平衡分区

稳定性：不稳定排序。相等的元素可能因分区而改变相对位置。

优点：

• 高效：在大多数情况下非常快，尤其是在内存访问模式上优于其他 O(n log n) 算法，如归并排序
• 就地排序：除了递归所需的栈空间外，几乎不需要额外空间

缺点：

• 不稳定：相等的元素可能因分区而改变相对位置
• 最坏情况性能：虽然不常见，但在已经几乎排序好的数组上表现不佳。可以通过随机选择基准来缓解

✨ 解题步骤详解

使用快速排序时：

1. 选择基准元素：最简单的方式是选第一个或最后一个元素。为了避免最坏情况，可以使用"三数取中"法（取首、中、尾三个元素的中位数）或随机选取。
2. 执行分区操作：将小于基准的元素放左边，大于等于基准的元素放右边。分区操作完成后，基准元素在其最终正确位置上。
3. 递归排序子数组：对基准左边和右边的子数组分别递归执行快速排序。
4. 确认终止条件：当子数组长度为 0 或 1 时，直接返回。

快速排序 vs 归并排序的选择：

• 需要稳定排序 → 用归并排序
• 内存受限、追求实际运行速度 → 用快速排序
• 数据接近有序 → 归并排序更优（快排可能退化为 O(n^2)）
• 竞赛中一般直接用 sort() 函数，底层通常是快速排序的优化版本

✨ 常见错误

• 基准选择不当导致最坏情况：如果数组已经有序（升序或降序），且每次选第一个元素做基准，分区会极度不平衡，导致时间复杂度退化为 O(n^2)。解决办法是随机选取基准或使用三数取中法。
• 分区循环条件中漏掉 left < right：内层 while 循环必须始终保持 left < right 的约束，否则指针可能交叉越界。
• 相等元素处理不当：如果数组中有大量相等元素，且分区时所有等于 base 的元素都被放到一边，会导致严重的不平衡。一种改进是"三路分区"：将数组分为 base 三部分。
• 忘记将 base 放回正确位置：分区操作最后必须将 base 放到 left==right 的位置，否则后续递归会遗漏这个元素。
• 数组越界：递归调用 quick_sort(a, left, mid-1) 时，如果 mid=0 则 mid-1=-1，需要确保 left >= right 时直接返回。

三、课后练习

编程练习

1. 病人排队：L3122