快速排序Quicksort

按枢轴分区，递归处理分区。

核心约束: 分区后两侧元素满足与枢轴的大小关系。
适用问题: 内存中通用排序及相关选择算法。
边界与取舍: 枢轴策略、重复值与最坏情况保护影响工程表现。

时间与空间#

n 为元素数；随机主元或随机打乱用于期望分析。

时间复杂度: 期望 $O(n \log n)$ ；最坏 $O(n^{2})$
辅助空间: 普通递归期望 $O(\log n)$ ，最坏 $O(n)$

原地分区通常不稳定。递归较短一侧并迭代较长一侧可把调用栈最坏压到 $O(\log n)$ ，但不会自动消除二次时间最坏情况。大量重复值适合三路分区。

基础原理参考资料

Princeton · Quicksort随机化分区、二次最坏情况和三路划分。