【一周一算法】第四周：快速排序

🧮 一周一个算法 · 第 4 周

快速排序（Quick Sort）——分治与随机化的完美结合

“归并是温和的分治，而快速排序，是分治的狂放之美。”
—— Donald E. Knuth

---

🧭 一、引言：快排的灵感来自哪？

归并排序将问题一分为二，然后合并两个有序序列。
但 Tony Hoare（快排的发明者）在 1960 年想到：

“为什么不在分割的时候就让它有序呢？”

于是，** 快速排序（Quick Sort）**诞生了。
它先选一个“枢轴”（pivot），
然后将小于 pivot 的放左边，大于的放右边，
再递归地对左右两侧进行排序。

结果？

• 无需“合并”阶段；
• 原地完成排序；
• 在平均情况下比归并排序更快！

---

⚙️ 二、算法思想

🧩 步骤概述：

1. 选择基准（pivot）
   从数组中选择一个元素作为“基准”。

2. 分区（partition）
   调整数组，使得：

   所有小于 pivot 的元素在左边；
   所有大于 pivot 的元素在右边。

3. 递归排序
   对左右两部分分别递归调用快速排序。

---

示例：

原始数组： [7, 2, 1, 6, 8, 5, 3, 4]

选 pivot = 4
分区后：   [2, 1, 3] [4] [7, 6, 8, 5]

再对子区间排序：
左：[1, 2, 3]
右：[5, 6, 7, 8]

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

---

📘 三、伪代码

procedure QuickSort(A, low, high):
    if low < high:
        pivot_index ← Partition(A, low, high)
        QuickSort(A, low, pivot_index - 1)
        QuickSort(A, pivot_index + 1, high)

Partition 操作：

procedure Partition(A, low, high):
    pivot ← A[high]
    i ← low - 1
    for j ← low to high - 1:
        if A[j] ≤ pivot:
            i ← i + 1
            swap(A[i], A[j])
    swap(A[i + 1], A[high])
    return i + 1

---

💻 四、C++ 实现（原地快排）

#include <iostream>
#include <vector>
#include <cstdlib> // for rand()

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素为基准
    int i = low - 1;

    for (int j = low; j < high; ++j) {
        if (arr[j] <= pivot) {
            std::swap(arr[++i], arr[j]);
        }
    }

    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main() {
    std::vector<int> arr = {7, 2, 1, 6, 8, 5, 3, 4};
    quickSort(arr, 0, arr.size() - 1);

    std::cout << "排序结果：";
    for (int num : arr) std::cout << num << " ";
    std::cout << std::endl;
}

输出：

排序结果：1 2 3 4 5 6 7 8

---

🧮 五、复杂度分析（数学视角）

1️⃣ 时间复杂度推导

假设每次划分都能平均分成两半：

$$T(n) = 2T(n/2) + O(n)$$

于是：

$$T(n) = O(n \log n)$$

但是——如果选的 pivot 特别糟糕（例如数组本身有序，pivot 选的是最大或最小）：

$$T(n) = T(n-1) + O(n) = O(n^2)$$

因此，快排的平均与最坏复杂度分别为：

情况	时间复杂度
最好	$O(n \log n)$
平均	$O(n \log n)$
最坏	$O(n^2)$

---

2️⃣ 空间复杂度

仅需递归栈空间：

$$S(n) = O(\log n) \quad \text{（平均情况）}$$

$$S(n) = O(n) \quad \text{（最坏情况）}$$

---

🎲 六、随机化快速排序（Randomized QuickSort）

为了防止“最坏情况”，
我们引入 随机化思想：

随机选择 pivot，而不是固定选最后一个。

随机化后的快排期望复杂度永远是：

$$\mathbb{E}[T(n)] = O(n \log n)$$

---

🌟 C++ 随机版实现

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

int randomizedPartition(std::vector<int>& arr, int low, int high) {
    int pivotIndex = low + rand() % (high - low + 1);
    std::swap(arr[pivotIndex], arr[high]);
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; ++j) {
        if (arr[j] <= pivot) {
            std::swap(arr[++i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void randomizedQuickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivotIndex = randomizedPartition(arr, low, high);
        randomizedQuickSort(arr, low, pivotIndex - 1);
        randomizedQuickSort(arr, pivotIndex + 1, high);
    }
}

int main() {
    srand(time(nullptr));
    std::vector<int> arr = {7, 2, 1, 6, 8, 5, 3, 4};
    randomizedQuickSort(arr, 0, arr.size() - 1);

    for (int x : arr) std::cout << x << " ";
    std::cout << std::endl;
}

---

🔢 七、数学深入：期望复杂度推导

定义 $T(n)$ 为对 $n$ 个元素排序的期望比较次数。

有递推式：

$$T(n) = n - 1 + \frac{1}{n} \sum_{k=0}^{n-1} \bigl(T(k) + T(n-k-1)\bigr)$$

经过推导可得：

$$T(n) = 2(n+1)H_n - 4n$$

其中 $H_n = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \approx \ln n + \gamma$。

因此：

$$T(n) = O(n \log n)$$

数学上，随机化保证了快排的“平均行为”稳定在 $O(n \log n)$。

---

⚙️ 八、工程实践优化

优化点	思想	效果
三数取中（median-of-three）	pivot = 中位数(首、中、尾)	避免极端划分
尾递归优化	避免深度递归栈	更节省内存
小区间插入排序	当 $n < 16$ 时改用插入排序	提高局部效率
内省排序（Introsort）	混合堆排序 + 快排	STL 的默认实现方式

---

🧠 九、思考与练习

1. 为什么随机化能保证期望 $O(n \log n)$？
2. 如何实现 非递归版 快速排序？
3. 为什么快排比归并排序更适合内存排序？
4. 归并和快排的“分治结构”本质差异是什么？

---

📚 十、延伸阅读

• 《算法导论》第 7 章：快速排序
• Tony Hoare, “Quicksort”, Computer Journal, 1962
• STL 源码阅读建议：std::sort（实现为 introsort）

---

✨ 十一、总结

特性	快速排序（Quick Sort）
平均时间复杂度	$O(n \log n)$
最坏时间复杂度	$O(n^2)$
空间复杂度	$O(\log n)$
是否稳定	❌ 不稳定
是否原地	✅ 是
适用场景	内存排序、数组、性能优先场景

快排是算法界的“黄金分割”——
简单、优雅、强大。
它代表了算法思想的成熟：数学 + 直觉 + 工程优化。

---

🔜 下周预告（第 5 周）

二分查找（Binary Search）进阶篇：数学视角下的对数查找与变体分析
我们将从“查找”的角度重新理解复杂度，并学习如何证明算法的正确性与边界稳定性。

---