数据结构与算法 / 系统课时
快速排序
快速排序
快速排序通过一次分区把基准放到最终位置,再递归处理左右区间。本课将用原地实现展示分区不变量、递归边界以及基准选择如何影响平均性能和最坏情况。
学习目标
- 解释快速排序的分区过程与递归边界
- 编写可运行的原地快速排序
- 分析基准选择、重复值与最坏情况
分区机制
本课采用闭区间 [low, high] 和 Lomuto 分区。先选择末尾元素作为基准,再扫描前面的元素,把不大于基准的值交换到左侧。扫描完成后,将基准放到左右两部分之间,它所在的位置已经确定,不应再次进入递归区间。
若每次分区接近均衡,递归树高度约为 ;若基准持续是当前区间的最小值或最大值,递归深度会增长到 ,时间复杂度退化为 。随机基准或三数取中能降低特定输入触发退化的概率。

主示例
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]复杂度与工程边界
平均情况下,每层分区处理 个元素,共约 层,因此时间复杂度为 ;最坏情况下为 。原地交换不需要长度为 的辅助数组,但递归栈平均占用 ,最坏可达 。
普通原地快速排序不稳定。大量重复值会使二路分区产生偏斜,三路分区可把数据划分为小于、等于和大于基准的三段。实现时还要统一区间定义,避免混用右开区间与闭区间。
按自己的节奏,确认真正理解。