快速排序动画

算法原理

快速排序（Quick Sort）是工业界最常用的排序算法。每轮从区间选一个基准（本动画取区间第一个元素），用 Hoare 原地划分把区间整理成「≤ 基准 | 基准 | ≥ 基准」三段——基准落到最终位置，左右两段再各自递归，分而治之。

Hoare 划分的节拍（动画严格按此演示）：

1. 双指针 i（后手，向右）、j（先手，向左）同时从区间两端出发；
2. j 先走，找 ≤ 基准 的元素停下；接着 i 走，找 > 基准 的元素停下——即「查一格挪一格」；
3. 两者都停下且 i < j：交换这一对（大的去右边、小的去左边），双指针各内收一格继续；
4. 当 i 撞上 j（i ≥ j）扫描结束，基准与 a[j] 交换——基准归位，它所在的位置就是最终答案，永不再动。

动画怎么看

卡片颜色是指针语言（页面右侧也有图例）：

• 橙色卡：当前基准，全屏唯一；归位后转深绿；
• 红色卡：本拍正在交换的一对，下一拍转浅绿；
• 浅绿卡：本轮已「归边」（确定属于基准某一侧）的元素；
• 深绿卡（带 ✓）：已全局终位，终身不褪色；
• i / j 圆徽章：双指针位置，→ / ← 箭头表示正在猎寻；交换时卡片间出现虚线 + ⇄。

动画下方有一行实时解说（如 ① p = 38 ｜ a[0..8)、j 停 ｜ 17 ≤ p、38 ⇄ 17 归位 a[0] ✓），结束时给出划分次数与互换次数。可以观察：基准归位后，它左右两段互相独立，递归树正是 O(log n) 层的来源。

复杂度分析

C++ 参考代码

#include <iostream>
#include <vector>
#include <utility>  // std::swap
using namespace std;

// Hoare 划分：返回基准最终落点，左侧都 ≤ 它，右侧都 ≥ 它
int partition(vector<int>& a, int lo, int hi) {
    int pivot = a[lo];          // 取区间第一个元素为基准
    int i = lo + 1, j = hi;
    while (true) {
        while (i <= j && a[i] <= pivot) i++;   // i 向右找 > pivot
        while (i <= j && a[j] >  pivot) j--;   // j 向左找 ≤ pivot
        if (i > j) break;
        swap(a[i], a[j]);                      // 一大一小换到两侧
    }
    swap(a[lo], a[j]);          // 基准与 a[j] 交换，归位
    return j;
}

void quickSort(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;       // 单元素 / 空区间天然有序
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);    // 左段递归
    quickSort(a, p + 1, hi);    // 右段递归
}

int main() {
    vector<int> a = {38, 17, 52, 9, 41, 25, 60, 13};
    quickSort(a, 0, a.size() - 1);
    for (int x : a) cout << x << ' ';   // 输出：9 13 17 25 38 41 52 60
    cout << endl;
    return 0;
}

什么时候用快速排序

快排是通用内存排序的默认答案：平均 O(n log n) 且常数小、原地排序、缓存局部性好，std::sort（配 Introsort 防退化）与多数语言内置排序的核心都是它。使用时要注意两点：不稳定（需要稳定时换 std::stable_sort）与最坏 O(n²)（工程上用三数取中、随机基准或Introsort 兜底）。CSP 阶段它是必默算法，第 k 大 / 荷兰国旗 / 三路划分等题都是划分思想的直接变体。