1. 分而治之先做划分
选定枢轴 pivot，把不大于它的元素分到左边，不小于它的分到右边；枢轴放到最终位置后，再分别排序两个子数组。相等键可能出现在两侧，不能把有重复值的例子理解为严格小于/大于。
2. 原文双指针划分的 Python 版本
def median_index(a, low, high, key=lambda x: x):
mid = (low+high)//2
return sorted([low, mid, high], key=lambda i: key(a[i]))[1]
def partition(a, low, high, key=lambda x: x, median=False):
if median:
p = median_index(a, low, high, key)
a[p], a[high] = a[high], a[p]
pivot = key(a[high])
i, j = low, high-1
while True:
while i <= j and key(a[i]) < pivot:
i += 1
while i <= j and key(a[j]) > pivot:
j -= 1
if i >= j:
break
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
a[i], a[high] = a[high], a[i]
return i
使用闭区间 [low, high]。pivot 在最右端，i 向右找不小于 pivot 的值，j 向左找不大于 pivot 的值。交换后两指针都前进，保证重复值时也能结束。最后交换 a[i] 与枢轴。教材显式检查边界，而不是依赖越界位置。
3. 递归版
def quick_sort(a, key=lambda x: x, median=False, cutoff=0):
def visit(low, high):
if low >= high:
return
if high-low+1 <= cutoff:
for i in range(low+1, high+1):
item, j = a[i], i
while j > low and key(a[j-1]) > key(item):
a[j] = a[j-1]
j -= 1
a[j] = item
return
p = partition(a, low, high, key, median)
visit(low, p-1)
visit(p+1, high)
visit(0, len(a)-1)
return a
终止条件 low >= high，同时覆盖空区间和单项；递归区间排除已经固定的枢轴，否则问题规模可能不缩小。
4. 比较、交换与递归树
一次划分工作为 O(m)，m 是当前区间长度。若分割比较均衡，深度约 log n，每层总工作 O(n)，平均时间 O(n log n)。若连续分成 n−1 与 0，总工作 1+2+…+(n−1)，为 O(n²)。
5. 枢轴策略与哨兵
固定最右值遇到升序数据容易退化。三数取中取左、中、右三项的中位值，不是平均数；仍不能保证避免所有最坏输入。随机枢轴可改善期望表现，但也不是逐次最坏 O(n log n) 保证。
原书右端 pivot 可作为左向右扫描的哨兵；本教材保留边界判断，更方便检查。Python a[-1] 合法，不意味着可以把负下标当成数组左边界保护。
6. 小区间切换插入排序
小区间上复杂划分的开销可能较大。可以设 cutoff，剩余小区间用插入排序。本例用 8 作演示参数，并非所有机器的最优阈值。
7. 显式栈和较短侧优先
def quick_sort_iterative(a, key=lambda x: x, median=True, cutoff=8):
stack = [(0, len(a)-1)]
while stack:
low, high = stack.pop()
while low < high:
if high-low+1 <= cutoff:
for i in range(low+1, high+1):
item, j = a[i], i
while j > low and key(a[j-1]) > key(item):
a[j] = a[j-1]
j -= 1
a[j] = item
break
p = partition(a, low, high, key, median)
if p-low < high-p:
if p+1 < high:
stack.append((p+1, high))
high = p-1 # 立即处理较短侧
else:
if low < p-1:
stack.append((low, p-1))
low = p+1
return a
将较长区间压栈，立即处理较短区间。每次立即进入的短侧规模至多约为原区间一半，待处理区间栈可控制在 O(log n)。这个改进控制空间，不能把坏枢轴导致的 O(n²) 时间变成 O(n log n)。
8. 稳定性与空间
该原地快排不稳定：[2A,2B,1X] 按末尾 1X 划分后可得到 [1X,2B,2A]。递归版平均栈 O(log n)，最坏 O(n)；较短侧优先的迭代版工作栈 O(log n)。这里的“原地”指不需要 O(n) 合并缓冲，不表示完全无栈空间。
9. 运行示例
a = [55,74,3,45,13,87,46,30]
print(quick_sort(a.copy()))
print(quick_sort_iterative(a.copy(), median=True, cutoff=8))
print(quick_sort([])) # []
print(quick_sort([5,5,5])) # [5,5,5]
10. 测试重点
空输入、单项、升序、降序、全相等、重复键、负数，以及划分后两侧的关系。不要把“快速排序”这个名称当作一定最快的保证。深递归在 Python 中可能触发 RecursionError，迭代版可以避免函数递归限制。