快速排序：选一个“班长”帮大家排好队

想象一下，体育老师要全班同学按身高从矮到高排成一队。老师先指定一个同学当“班长”（基准），然后让所有比他矮的同学站到左边，所有比他高的同学站到右边。这样一来，班长就站在了最终正确的位置上。接着，老师对左边的“小个子组”和右边的“高个子组”重复同样的操作（再各选一个班长），直到每个组只有一个人，队伍就排好了。

快速排序（Quick Sort）用的就是这种“分而治之”的思想。它能在平均情况下非常高效地给一堆数据排好序，是C++标准库std::sort的默认算法之一。下面我们来一步步拆解它。

1. 快速排序的核心步骤

把整个排队过程翻译成计算机语言，快速排序分三步走：

选基准：从数组里挑一个元素当“分界点”，也就是班长。通常选第一个、最后一个，或者随机选一个。
分区：通过交换元素，把比基准小的全部挪到左边，比基准大的全部挪到右边。分区结束后，基准就待在了它最终该待的位置上（就像班长站对位置后就不再移动）。
递归：对基准左边和右边的两个子数组重复上述过程，直到每个子数组只剩一个元素（此时整个数组已经有序）。

注意：整个交换过程都在原数组上进行，不需要额外开一个大数组来存放，所以快速排序是一种原地排序。

2. 生活例子：用成绩排名来理解

假设你的班级有5位同学的数学成绩：[78, 92, 65, 88, 70]，想按从低到高排序。

选基准：选第一个同学的成绩78当“班长”。
分区：
- 从左到右找第一个大于78的成绩：92（在位置2）。
- 从右到左找第一个小于等于78的成绩：70（在位置5）。
- 交换92和70，数组变成[78, 70, 65, 88, 92]。
- 继续：左指针继续找下一个大于78的：88（位置4），右指针找小于78的：65（位置3）。交换88和65，数组变成[78, 70, 65, 88, 92]？不对，此时左指针在位置4，右指针在位置3，左指针超过了右指针，停止扫描。
- 把基准78（位置1）和右指针指向的65（位置3）交换，得到[65, 70, 78, 88, 92]。现在基准78已经在它最终的位置上（第3位）。
递归：
- 左边子数组[65, 70]：选65为基准，分区后得到[65, 70]。
- 右边子数组[88, 92]：选88为基准，分区后得到[88, 92]。
最终数组有序：[65, 70, 78, 88, 92]。

3. 图解分区过程（重要！）

为了帮助理解，我们一步步看上面例子中分区的具体操作。用两个指针i（左指针，从第二个元素开始）和j（右指针，从最后一个元素开始）向中间移动，找到需要交换的一对元素。

初始数组: [78, 92, 65, 88, 70]  基准pivot = 78
位置:      1   2   3   4   5
         low                high
         i=2                j=5

第一步：i向右找 >78的 → i停在2（92）
        j向左找 ≤78的 → j停在5（70）
        交换 arr[2]和arr[5] → [78, 70, 65, 88, 92]

第二步：i继续向右找 >78的 → i停在4（88）
        j向左找 ≤78的 → j停在3（65）
        此时i=4, j=3，i>j，停止扫描

第三步：把基准（位置1）与arr[j]（位置3的65）交换
        → [65, 70, 78, 88, 92]  基准78到达正确位置(3)

注意：交换基准后，arr[3]=78的位置就是以后再也不会变的位置。

4. 常见错误（新手最容易踩的坑）

错误1：分区时忘记处理重复元素
如果数组里有和基准相等的元素，必须统一放到左边或右边，否则可能导致无限递归。上面的代码把小于等于基准的元素留在左边（arr[i] <= pivot时左指针右移），大于基准的留在右边（arr[j] > pivot时右指针左移），这样相等元素会均匀分布在基准两侧，不会出问题。

错误2：分区循环条件写错（死循环或越界）
比如把内层while的i <= j写成i < j，或者把arr[i] <= pivot写成arr[i] < pivot，都可能造成指针越界。一定要保证在指针相遇前能正确停止。

错误3：递归基准位置用错
分区函数返回的j是基准的最终索引，递归左边应该是low到pi-1，右边是pi+1到high。如果把基准自己也递归进去，就会无限递归。

错误4：数组只有1个元素或为空时没有检查
递归函数quickSort一开始有if (low < high)判断，确保至少有两个元素才继续，否则直接返回。这是必需的。

5. 完整可运行的C++代码（带详细中文注释）

下面是用最左边元素作为基准，用两个指针扫描的完整实现。代码中每行变量定义都有中文注释，方便理解。

#include <iostream>
using namespace std;

// 分区函数：把数组分成左边小、右边大，返回基准最终位置
int partition(int arr[], int low, int high) {
    int pivot = arr[low];        // 选最左边为基准（班长）
    int i = low + 1;             // 左指针，从基准右边开始
    int j = high;                // 右指针，从最右边开始

    while (i <= j) {
        // 左指针向右移动，找到第一个大于基准的元素
        while (i <= j && arr[i] <= pivot) i++;
        // 右指针向左移动，找到第一个小于等于基准的元素
        while (i <= j && arr[j] > pivot) j--;
        if (i < j) {
            // 交换这一对大一个小元素，让它们各归其位
            swap(arr[i], arr[j]);
        }
    }
    // 把基准放到正确位置（j所指的位置）
    swap(arr[low], arr[j]);
    return j;  // 返回基准的新位置
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 1. 分区，得到基准的最终位置pi
        int pi = partition(arr, low, high);
        // 2. 递归排序左边部分（比基准小的）
        quickSort(arr, low, pi - 1);
        // 3. 递归排序右边部分（比基准大的）
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    // 用零花钱金额（元）举个栗子：小红有10元，小刚7元，小明8元，小丽9元，小强1元，小美5元
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);  // 数组长度
    
    quickSort(arr, 0, n - 1);  // 对整个数组排序
    
    cout << "排序结果（从少到多）: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    // 输出：1 5 7 8 9 10
    return 0;
}

运行程序，你会看到输出：

排序结果（从少到多）: 1 5 7 8 9 10

6. 快速排序快在哪里？

快速排序的平均时间复杂度是 O(n log n)，最坏情况（比如每次选到的基准都是最小或最大）会退化成 O(n²)，但通过随机选基准或者三数取中法可以避免。而且由于它交换次数少、缓存友好，实际运行起来往往比归并排序和堆排序还要快，所以C++标准库的std::sort混合了快速排序、插入排序和堆排序，在大多数场景下表现极佳。

7. 相关知识点指引

递归的思想：快速排序通过递归不断缩小问题规模，理解递归是掌握快速排序的前提。
分治算法：除了快速排序，还有归并排序、二分查找、汉诺塔问题等都用到了“分而治之”的策略。
std::sort：C++标准库的排序函数，内部使用了快速排序的变种，实际编程中直接调用#include <algorithm>和sort(arr, arr+n)即可。
随机化快速排序：通过随机选取基准来避免最坏情况，感兴趣的话可以尝试修改partition函数。

如果你已经掌握了快速排序，不妨动手试试：改成随机选基准，或者用三路快排（处理含有大量重复元素的情况），你会在实践中加深理解。

例题精讲