快排性能分析
看完你能说清快排的最坏、平均复杂度从哪来，以及它为何不稳定
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
快排性能分析
看完你能说清快排的最坏、平均复杂度从哪来，以及它为何不稳定
不稳定是什么意思
上一页我们说快排平均 O(n log n)，但还有个常被追问的短板：它是不稳定排序。不稳定听起来抽象，其实拿两个相等的元素排一下序，位置对不上了，问题就现形了。
票价相同的两人，排在前面的人不应被插队到后面
快排为何不稳定
跟踪两个相等元素在划分中如何被换到远端、次序颠倒。
就地：O(1)辅助空间
前面看了快排的时间和不稳定性，还有个常被忽略的问题：它排序百万个数字时，额外要多占多少内存？答案是几乎不用——它不另开新数组，就在原来的数组里翻来换去。
案板上的食材直接调换位置，不另拿一个盘子来装
不稳定+就地意味着什么
「不稳定」和「就地」是一对交换得来的性质：快排用前者换来后者。什么时候这交换划算？
- 相等元素保持原相对顺序
- 需 O(n) 辅助空间
- 按多字段二次排序不出错
- 相等元素顺序被打乱
- O(1) 辅助空间，原地交换
- 排原始数值/日志时无感知差异
性能由什么决定
前面说了快排就地又不稳定，那速度呢？回想划分过程：每一层都要把整个数组的元素扫一遍，代价约 O(n)。所以总耗时 = 每层代价 × 层数——层越少越快，层越多越糟。
从中间对半切，刀数最少；每次只切下一小片，刀数暴增
最好情况：均匀划分
每次枢轴居中，递归树深度 log n，层层画出均衡划分树
最坏情况：划分一边倒
对比两棵递归树：均匀划分树矮而宽，一边倒树高n层。沿箭头看每层剩多少元素。
最坏情形的代价累加
用代码逐层累加比较次数，验证一边倒划分时代价为何是 n(n+1)/2。
逐层累加 n+(n-1)+…+2，正是等差求和的前 n 项，计数结果落在 n(n+1)/2 量级。
平均情况怎么定义
前面看到最好 O(nlogn)、最坏 O(n²)，差在哪？就在每次划分的枢轴位置。真实的枢轴时好时坏，那长期跑下来到底算谁？这就得给「平均」一个严格的说法：取期望。
单程可能一路绿灯或全红灯，但长期通勤时间取期望后稳定
期望递归深度的直觉
从上往下看：每层抽枢轴像掷硬币，攒到一次「好枢轴」规模就缩水，深不到哪里去。
最坏 vs 平均：0.618 之差
同为快排，n log n 和 n² 只差一个划分平衡——但平均常数的来源常被讲错。
- 划分位置均匀分布，非全对称
- 期望比较次数约 1.39 n log n
- 1.39 源自 2(1+ln2)≈1.386
- 划分一边倒，如已有序取端点
- 每层只消一个元素，代价累加
- 总比较达 n(n-1)/2 ≈ n²/2
三条结论一张表
- ✓工程定位：不稳定+就地，适合内部排序、可接受乱序的场景
- ✓性能取决于划分质量：划分越均衡，递归树越浅
- ✓最好/平均 O(n log n)，最坏 O(n²) 可靠随机化选主元规避
- ✓平均与最好只差常数因子，实践中接近理想
自测：哪种输入最坏
下列哪种输入会让采用固定首元素为基准的快排达到最坏时间复杂度？
课后思考
先自己想一会儿，再看参考答案——答案只是思考路径的起点。
参考答案回顾三条结论：平均性能好、就地省空间、常数小。补救思路：给元素附下标当次关键字，或改用归并/插入混合。核心是权衡，不是谁全面胜出。
参考答案随机会破坏算法的确定性：测试难复现、有实时性要求的系统忌讳最坏波动。工程上常在随机化、三数取中、introsort 兜底之间按场景取舍。
参考答案看场景：单次排序差 2.4 倍可接受，但恶意构造的输入可让线上服务被DoS，且最坏在深层递归中还拖垮缓存。重复调用、输入不可信时，防最坏就是刚需。