知识卡片

普通读书笔记卡 · 4545.g.11.c.1.e.11.h

枢轴划分后递归子区间

理解等级:中级

快速排序选择一个枢轴,把其他元素分到相对它较小与较大的两侧,再分别处理子区间。关键是分区后枢轴位置正确,且递归处理范围逐步缩小。

本书给出以首元素为枢轴的填位式实现,但其循环和下标边界不能作为正确模板,空切片也会直接访问第0项。应理解划分与递归的职责,再核对终止和访问边界,不能从三个展示用例推断任意输入都正确。

这张卡片看不懂?

已有反馈 · 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