知识卡片
枢轴划分后递归子区间
快速排序选择一个枢轴,把其他元素分到相对它较小与较大的两侧,再分别处理子区间。关键是分区后枢轴位置正确,且递归处理范围逐步缩小。
本书给出以首元素为枢轴的填位式实现,但其循环和下标边界不能作为正确模板,空切片也会直接访问第0项。应理解划分与递归的职责,再核对终止和访问边界,不能从三个展示用例推断任意输入都正确。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
func quickSort(values [] int, left, right int) { temp := values[left] p := left i, j := left, right for i <= j
参考来源
- 位置:《Go语言编程 完整版》第02章《顺序编程》(来源项目book-sources:extracted/Go语言编程 完整版/_epub-src/text/part0000_split_001.html;spine 2,归一字符[3527,3637))
- 结论依据:原文以temp保存首元素并在分区后递归左右区间;对可见边界问题明确限制,不照抄为成熟实现。
- 原始内容:func quickSort(values [] int, left, right int) { temp := values[left] p := left i, j := left, right for i <= j