8.3.2.1 快速排序的性能与应用

教材导航 · 第8章

原书定位

印刷页P350起,对应PDF第362页。下文为目视整理的知识提要;完整内容见原书对照。

划分均衡时递推 T(n)=2T(n/2)+O(n)T(n)=2T(n/2)+O(n),最好与平均时间 O(nlog⁡n)O(n\log n);每次枢轴都处于一端时最坏 O(n2)O(n^2)。首元素作枢轴时,已有序或逆序可能导致最坏划分。

普通递归的栈空间平均 O(log⁡n)O(\log n)、最坏 O(n)O(n);一次原地划分只用 O(1)O(1),不代表整个递归排序也只用常量空间。不稳定,教材双指针数组实现依赖随机访问。

随机枢轴、三数取中可改善常见数据上的划分,但不消除理论最坏情况。只递归目标所在一侧可做快速选择,期望 O(n)O(n) 求第 kk 小;三路划分还可用于荷兰国旗问题。

对应练习

8.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P350,PDF第362页