第 16 课 - 快速排序 (Quick Sort)

课程定位： 数据结构与算法 | 排序算法模块 | 中级难度 标签： quick-sort, pivot, partition, in-place

1. 学习目标

通过本课程的学习，你将能够：

理解快速排序基于“分治法”的基本思想与排序流程。
掌握核心操作“分区（Partition）”的原理和实现方法。
分析快速排序的平均时间复杂度、空间复杂度及其优缺点。
实现一个标准的快速排序算法，并能处理边界情况。

2. 核心概念

快速排序（Quick Sort）是应用最广泛的排序算法之一，其核心思想是 “分而治之”。

想象一下，你要整理一堆乱序的书籍。你的做法是：

选基准：先从书中抽出一本作为“基准书”（Pivot）。
分区：把所有比“基准书”薄的放左边，比它厚的放右边。
递归：现在，你有了“左边一堆”、“基准书”、“右边一堆”。对左边和右边那两堆书，重复上述步骤，直到每一堆都只剩一本书。这时，整个书架就自然有序了。

这就是快速排序的精髓：通过一次分区操作，将问题规模缩小，然后递归处理子问题。

关键点：原地排序 (In-Place) 一个优秀的快速排序实现是 原地排序 的。这意味着它不需要像归并排序那样，额外开辟一个与原数组等大的空间来合并数据。所有操作都在原始数组上进行，通过元素交换来实现，空间效率非常高。

分区 (Partition) 操作详解 这是快排的灵魂。我们选取一个元素作为“基准”（通常选第一个、最后一个或随机元素），然后扫描数组，确保：

基准左侧的元素都 ≤ 基准值
基准右侧的元素都 > 基准值操作完成后，基准元素就落在了它最终应该在的位置上。

3. 代码示例

下面我们使用 Lomuto 分区方案（选取最后一个元素为基准）来实现快速排序。这种方案逻辑清晰，易于理解。

def quick_sort(arr):
    """快速排序的主函数"""
    # 调用递归排序函数，初始范围是整个数组
    _quick_sort_recursive(arr, 0, len(arr) - 1)
    return arr

def _quick_sort_recursive(arr, low, high):
    """递归排序函数"""
    # 递归基准情况：如果子数组的起始索引大于等于结束索引，说明已排序或为空，直接返回
    if low < high:
        # 执行分区操作，得到基准元素的最终位置
        pivot_index = partition(arr, low, high)
        # 递归排序基准左侧的子数组
        _quick_sort_recursive(arr, low, pivot_index - 1)
        # 递归排序基准右侧的子数组
        _quick_sort_recursive(arr, pivot_index + 1, high)

def partition(arr, low, high):
    """
    Lomuto 分区函数
    参数:
        arr: 待排序数组
        low: 子数组起始索引
        high: 子数组结束索引
    返回:
        pivot_index: 基准元素最终所在的正确索引
    """
    # 选择最后一个元素作为基准
    pivot = arr[high]
    # i 指向“小于等于 pivot”区域的末尾，初始时该区域为空，所以在 low 之前
    i = low - 1
    
    # j 从 low 开始扫描，直到 high-1（最后一个元素是基准，不需要比较）
    for j in range(low, high):
        # 如果当前元素小于等于基准
        if arr[j] <= pivot:
            # 扩展“小于等于 pivot”的区域：i 前移一位
            i += 1
            # 将 arr[j] 交换到区域末尾
            arr[i], arr[j] = arr[j], arr[i]
    
    # 循环结束后，i 指向“小于等于 pivot”区域的最后一个元素
    # 将基准元素 (arr[high]) 与该区域的下一个位置 (arr[i+1]) 交换
    # 这样，基准就落到了正确的位置上
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    # 返回基准的最终位置
    return i + 1

# 测试代码
if __name__ == "__main__":
    sample_array = [8, 3, 1, 7, 0, 10, 2]
    print("原始数组:", sample_array)
    sorted_array = quick_sort(sample_array)
    print("排序结果:", sorted_array)
    
    # 测试另一个数组
    sample_array2 = [5, 5, 5, 3, 3, 1]
    print("\n原始数组:", sample_array2)
    sorted_array2 = quick_sort(sample_array2)
    print("排序结果:", sorted_array2)

运行结果：

原始数组: [8, 3, 1, 7, 0, 10, 2]
排序结果: [0, 1, 2, 3, 7, 8, 10]

原始数组: [5, 5, 5, 3, 3, 1]
排序结果: [1, 3, 3, 5, 5, 5]

4. 实践练习

练习一（基础）： 给定数组 [4, 6, 2, 8, 1, 9, 3]，请手动模拟第一轮分区（以最后一个元素 3 为基准）后数组的状态，并写出基准元素 3 的最终索引。

练习二（中等）： 修改上面的代码，使其使用“第一个元素”作为基准（Hoare分区方案的思路）。注意调整分区函数 partition 的逻辑，并测试其对已排序数组 [1, 2, 3, 4, 5] 的表现。思考：这可能导致什么问题？

练习三（挑战）： 快速排序对于包含大量重复元素的数组效率可能会降低。请你实现一个 “三路快排” (Dutch National Flag partitioning) 的分区函数 partition_three_way(arr, low, high)，将数组分为 < pivot、== pivot、> pivot 三个部分，并返回两个边界索引 lt, gt，使得 arr[low..lt-1] < pivot, arr[lt..gt] == pivot, arr[gt+1..high] > pivot。

5. 常见错误

忘记处理递归基准情况： 递归函数中没有 if low < high 的判断，会导致无限递归或索引越界错误。
分区边界错误： 在 partition 函数中，i 和 j 的初始值、循环范围（range(low, high) 还是 range(low, high+1)）需要仔细核对，这是最容易出错的地方。
误以为它是稳定排序： 快速排序是不稳定的排序算法。因为在交换元素时，相等元素的相对顺序可能会被改变。例如，对 [(1,‘A’), (1,‘B’), (2,‘C’)] 按第一个值快排，(1,‘B’) 可能被交换到 (1,‘A’) 的前面。
最坏情况退化： 当数组已经有序或逆序，且每次选择第一个或最后一个元素作为基准时，分区会极度不平衡（一边0个元素，一边n-1个元素），导致时间复杂度退化为 O(n²)。可以通过 “随机选取基准” 或 “三数取中法” 来优化。
递归深度过深： 对于一个很大的数组，如果分区极不平衡，递归调用栈会很深，可能在Python等语言中导致 RecursionError。这时可以考虑改用迭代方式，或对小子数组改用插入排序。

6. 小结

本课我们学习了高效且广泛应用的快速排序算法。

核心思想：分治法，通过选择一个“基准”，将数组分区为左右两部分，并递归排序子数组。
关键操作：分区 (Partition)，它确定了基准的最终位置，并使得左侧元素均不大于基准，右侧元素均大于基准。
性能：
- 平均时间复杂度：O(n log n)，效率非常高。
- 最坏时间复杂度：O(n²)，通过优化基准选择可避免。
- 空间复杂度：O(log n) (递归栈空间)，是原地排序算法。
优缺点：
- 优点：平均性能极好，缓存命中率高，实际应用中通常是最快的排序算法之一。
- 缺点：不稳定，最坏情况性能差（可优化），递归深度可能较大。

与归并排序对比：快排在分区时做足工作（确保有序性），而合并时非常简单；归并排序则在分区时直接切分，合并时做足工作。快排通常是“首选”的通用排序算法，但如果你需要稳定排序，归并排序可能是更好的选择。下一课，我们将学习另一种基于“分治”思想，但侧重于“选择”的排序算法——堆排序。

练习编辑器

rust