算法入门 · 01
快速排序：
把大问题分成小问题
先找一个参照，把小的放左边、大的放右边。然后，对两边重复同一件事。
01 先分组，再排序
假设桌上有一叠写着数字的卡片。与其一开始就找出每张卡片的最终位置，不如先挑一个数作为基准（pivot），把剩下的数分组。
左右两组内部还没排好，但它们与基准的大小关系已经确定。
接着，分别排序左边的 [3, 1, 2, 4] 和右边的 [8, 7, 6]。当一组只剩零个或一个数字时，就不需要再排序了。最后按“左组 + 等于基准的组 + 右组”的顺序拼起来。
02 看一次完整的排序
下面的演示每次选择当前分组中间位置的数字作为基准。点击“下一步”，观察分组如何缩小，再逐层合并。这里使用便于理解的三路分组，不演示原地交换。
初始数组尚未排序。第一轮将选择 5 作为基准。
查看已执行的步骤
03 用几行代码表达它
这份 Python 实现强调可读性：把小于、等于、大于基准的数字分别装进三个新列表，再递归处理左右两组。
def quicksort(values):
if len(values) <= 1:
return values
pivot = values[len(values) // 2]
less, equal, greater = [], [], []
for value in values:
if value < pivot:
less.append(value)
elif value > pivot:
greater.append(value)
else:
equal.append(value)
return quicksort(less) + equal + quicksort(greater)
print(quicksort([8, 3, 1, 7, 5, 2, 6, 4]))
# [1, 2, 3, 4, 5, 6, 7, 8]把等于基准的数字单独分组，可以避免对这些重复值继续递归。注意：中间位置的数不一定是中位数，这样选择并不能保证两边一样大。
04 为什么通常很快？
一次分区需要扫描当前分组。如果每次分得比较均匀，问题规模就会不断减半，递归深度约为 log₂ n；每一层的扫描量合计不超过 O(n)，总时间便是 O(n log n)。
在常见的随机输入模型下，平均达到这个量级。
每次基准都接近最小或最大值，只减少很少的待排序元素。
工程实现常用随机选基准或“三数取中”来减少糟糕分区，也可能在递归过深时切换其他排序算法。随机化能降低遇到坏情况的概率，但不消除理论上的最坏情况。
别忽略空间和稳定性
上面的教学代码会新建列表，并非原地排序。分区均衡时，额外空间的峰值为 O(n)；极端不均衡时，递归层保留的列表可能使峰值达到 O(n²)，也可能先触发 Python 的递归深度限制。
常见的原地快速排序通常不稳定：两个键值相同的记录，排序后可能交换先后顺序。本文这种按扫描顺序追加的三路实现，若按记录的键比较，可以保留相等记录的原有顺序。稳定性取决于具体实现。