GESP 4级 · 快速排序

📖概念讲解

【考点 · 4级】快速排序（Quick Sort）— 基于分治思想的高效排序算法，属于排序算法类。

【说人话】核心就三步：① 选一个基准元素（pivot）；② 把数组分成两半——比 pivot 小的放左边，大的放右边（这一步叫"分区"partition）；③ 对左右两半递归调用。

⚡ 易错提醒：递归终止条件必须写对！当 l >= r 时要 return，否则无限递归导致栈溢出。另外 pivot 的选择也很关键——选首元素最简单，但如果数组已经有序会退化到 O(n²)。

💻代码示例

标准快速排序（选首元素为 pivot，双指针分区）：

#include <iostream>
using namespace std;
// 快排核心：把 arr[l..r] 按 pivot 分成左右两半
int partition(int arr[], int l, int r) {
    int pivot = arr[l];          // 取首元素作为基准
    int i = l, j = r;           // i 左指针, j 右指针
    while (i < j) {
        // 从右往左找比 pivot 小的元素
        while (i < j && arr[j] >= pivot) j--;  // j 往左移
        // 从左往右找比 pivot 大的元素
        while (i < j && arr[i] <= pivot) i++;  // i 往右移
        if (i < j) swap(arr[i], arr[j]);     // 交换这两个元素
    }
    swap(arr[l], arr[i]);        // 把 pivot 放到最终位置 i
    return i;                     // 返回 pivot 的最终下标
}
// 递归快排：对 arr[l..r] 排序
void quickSort(int arr[], int l, int r) {
    if (l >= r) return;              // ⚠️ 递归终止：只有一个或没有元素
    int pos = partition(arr, l, r);  // 分区，拿到 pivot 位置
    quickSort(arr, l, pos - 1);     // 递归排左半部分
    quickSort(arr, pos + 1, r);     // 递归排右半部分
}
int main() {
    int arr[] = {3, 6, 1, 8, 2, 5, 4, 7};
    int n = 8;
    quickSort(arr, 0, n - 1);        // 从下标 0 排到 n-1
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";      // 输出排序结果
    return 0;
}
// 输出: 1 2 3 4 5 6 7 8

📊 复杂度：平均 O(n log n)，最坏 O(n²)（数组已有序时退化），空间 O(log n)（递归栈）。快排是 C++ 标准库 std::sort 的底层实现之一！

🧩互动小测

题 1：快速排序的平均时间复杂度是？

题 2：快排最坏时间复杂度 O(n²) 在什么情况下出现？

题 3：快排中 partition 函数的作用是？

🏋️动手练一练

📝 编程练习

给定一个整数数组，用快速排序将其按从大到小（降序）排列。
输入：第一行一个整数 n，第二行 n 个整数。
输出：降序排列后的数组，用空格分隔。
提示：只需要把 partition 中的比较方向反过来（找比 pivot 大的放左边、小的放右边）。

参考答案：

#include <iostream>
using namespace std;

int partition(int arr[], int l, int r) {
    int pivot = arr[l];       // 取首元素作基准
    int i = l, j = r;
    while (i < j) {
        // ⬇️ 改成从右找比 pivot 小的（降序）
        while (i < j && arr[j] >= pivot) j--;
        while (i < j && arr[i] <= pivot) i++;
        if (i < j) swap(arr[i], arr[j]);
    }
    swap(arr[l], arr[i]);
    return i;
}

void quickSort(int arr[], int l, int r) {
    if (l >= r) return;
    int pos = partition(arr, l, r);
    quickSort(arr, l, pos - 1);
    quickSort(arr, pos + 1, r);
}

int main() {
    int n, arr[100];
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;
}

要点：降序排列只需修改比较方向。注意题目要求输入 n 再读数组，别搞混输入顺序。

📝易错点提醒

递归终止条件：必须是 l >= r，不是 l > r。l == r 时只有一个元素，无需排序。
双指针顺序：必须先从右往左（j--），再从左往右（i++）。顺序反了会导致 pivot 位置不对。
边界条件：i 和 j 移动时都要加上 i < j 的判断，防止越界。
最坏情况：如果每次 pivot 都选到最小/最大值，退化为 O(n²)。实际工程中会用随机选 pivot 或"三数取中"来优化。
不稳定排序：快排是不稳定的——相同元素的相对顺序可能改变。需要稳定排序时用归并排序。

📘快速排序

📖概念讲解

💻代码示例

🧩互动小测

题 1：快速排序的平均时间复杂度是？

题 2：快排最坏时间复杂度 O(n²) 在什么情况下出现？

题 3：快排中 partition 函数的作用是？

🏋️动手练一练

📝 编程练习

📝易错点提醒