形式陈述

快速排序选择枢轴，把数组原地划分为不大于与不小于枢轴的区域，再递归排序两侧。一次划分为 $\Theta(n)$$\mathrm{\Theta }(n)$。若每次划分规模为 $k$$k$ 与 $n-k-1$$n-k-1$，递推为

$$ T(n)=T(k)+T(n-k-1)+\Theta(n). $$$$T(n)=T(k)+T(n-k-1)+\mathrm{\Theta }(n).$$

极端不平衡导致最坏 $\Theta(n^2)$$\mathrm{\Theta }(n^2)$；枢轴均匀随机时，对任意固定输入的期望比较数为 $\Theta(n\log n)$$\mathrm{\Theta }(n\log n)$。常见原地实现只需递归栈，期望深度 $O(\log n)$$O(\log n)$，但最坏可为 $O(n)$$O(n)$，且通常不稳定。

直觉

先把一个枢轴放到最终相对位置，并在原数组中把小键和大键分开；性能取决于划分是否持续均衡。

例子与边界

总选首元素处理已排序数组会不断产生 $0$$0$ 与 $n-1$$n-1$ 划分而平方退化；随机枢轴可消除输入顺序与坏划分的固定关联。大量重复键时，二路划分可能低效，三路划分把等于枢轴的元素集中处理。随机化结论是对算法随机性的期望，不等于每次运行保证 $O(n\log n)$$O(n\log n)$。

推论与应用

快速排序因缓存局部性和低常数常用于内存排序；工程实现会结合小数组插入排序、三数取中和深度上限，后者形成 introsort 以恢复最坏 $O(n\log n)$$O(n\log n)$。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Ch. 7, quicksort, randomized analysis, and partitioning。
• Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998，Vol. 3, §5.2.2, sorting by exchanging。