数据结构与算法 / 系统课时

快速排序

快速排序

快速排序通过一次分区把基准放到最终位置,再递归处理左右区间。本课将用原地实现展示分区不变量、递归边界以及基准选择如何影响平均性能和最坏情况。

学习目标

  • 解释快速排序的分区过程与递归边界
  • 编写可运行的原地快速排序
  • 分析基准选择、重复值与最坏情况

分区机制

本课采用闭区间 [low, high] 和 Lomuto 分区。先选择末尾元素作为基准,再扫描前面的元素,把不大于基准的值交换到左侧。扫描完成后,将基准放到左右两部分之间,它所在的位置已经确定,不应再次进入递归区间。

若每次分区接近均衡,递归树高度约为 log⁡n\log n;若基准持续是当前区间的最小值或最大值,递归深度会增长到 nn,时间复杂度退化为 O(n2)O(n^2)。随机基准或三数取中能降低特定输入触发退化的概率。

快速排序分区与递归区间

主示例

python
def partition(items, low, high):
    pivot = items[high]
    smaller_end = low - 1

    # [low, smaller_end] 始终保存不大于基准的元素。
    for current in range(low, high):
        if items[current] <= pivot:
            smaller_end += 1
            items[smaller_end], items[current] = (
                items[current],
                items[smaller_end],
            )

    pivot_index = smaller_end + 1
    items[pivot_index], items[high] = items[high], items[pivot_index]
    return pivot_index

def quick_sort(items, low, high):
    if low >= high:
        return

    pivot_index = partition(items, low, high)
    # 基准已经在最终位置,递归时必须排除它。
    quick_sort(items, low, pivot_index - 1)
    quick_sort(items, pivot_index + 1, high)

data = [10, 7, 8, 9, 1, 5]
quick_sort(data, 0, len(data) - 1)
print("排序结果:", data)

预期输出:

text
排序结果: [1, 5, 7, 8, 9, 10]

复杂度与工程边界

平均情况下,每层分区处理 nn 个元素,共约 log⁡n\log n 层,因此时间复杂度为 O(nlog⁡n)O(n\log n);最坏情况下为 O(n2)O(n^2)。原地交换不需要长度为 nn 的辅助数组,但递归栈平均占用 O(log⁡n)O(\log n),最坏可达 O(n)O(n)。

普通原地快速排序不稳定。大量重复值会使二路分区产生偏斜,三路分区可把数据划分为小于、等于和大于基准的三段。实现时还要统一区间定义,避免混用右开区间与闭区间。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

快速排序

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通