8.3.2 快速排序
原书定位
印刷页P348起,对应PDF第360页。下文为目视整理的知识提要;完整内容见原书对照。
选枢轴,将区间划成关键字不大于枢轴和不小于枢轴的两部分,使枢轴到最终位置,再递归处理左右区间。一次划分的两边各自未必有序。
教材采用首元素作枢轴的双指针挖坑法:先从右找较小元素填左坑,再从左找较大元素填右坑,交替推进,指针相遇后填回枢轴。等值元素的比较条件和指针推进须与实现一致,避免停滞。

一次快速划分的双指针移动,原书P348。

快速排序递归树,原书P349。
下级知识点
对应练习
关联知识
- 3.3.3 栈在递归中的应用
- 5.3.1 二叉树的遍历
- 6.3.2 深度优先搜索
- 7.2.2 折半查找
- 8.3 交换排序
- 8.3.1 冒泡排序
- 8.3.2.1 快速排序的性能与应用
- 8.5.1 归并排序
原书对照
展开原书对照截图


