8.3.2.1 快速排序的性能与应用
原书定位
印刷页P350起,对应PDF第362页。下文为目视整理的知识提要;完整内容见原书对照。
划分均衡时递推 ,最好与平均时间 ;每次枢轴都处于一端时最坏 。首元素作枢轴时,已有序或逆序可能导致最坏划分。
普通递归的栈空间平均 、最坏 ;一次原地划分只用 ,不代表整个递归排序也只用常量空间。不稳定,教材双指针数组实现依赖随机访问。
随机枢轴、三数取中可改善常见数据上的划分,但不消除理论最坏情况。只递归目标所在一侧可做快速选择,期望 求第 小;三路划分还可用于荷兰国旗问题。
对应练习
关联知识
原书对照
展开原书对照截图
