8.3.2 快速排序

教材导航 · 第8章

原书定位

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

选枢轴,将区间划成关键字不大于枢轴和不小于枢轴的两部分,使枢轴到最终位置,再递归处理左右区间。一次划分的两边各自未必有序。

教材采用首元素作枢轴的双指针挖坑法:先从右找较小元素填左坑,再从左找较大元素填右坑,交替推进,指针相遇后填回枢轴。等值元素的比较条件和指针推进须与实现一致,避免停滞。

一次快速划分的双指针移动

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

快速排序递归树

快速排序递归树,原书P349。

下级知识点

对应练习

8.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P348,PDF第360页

原书对照,原书P349,PDF第361页

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