知识卡片

普通读书笔记卡 · 5626.i

选择最小项扩张有序前缀

理解等级:中级

选择排序每轮扫描尚未排序的后缀,记录最小值位置,与后缀首位交换,使有序前缀增加一项。即使输入原已排序,仍按相同边界完成候选比较。

比较总数为n(n-1)/2,最坏和最好都平方阶;原书计数公式有误但阶数不变。交换可能跨过相等元素,故该实现不稳定;使用常数索引变量,不需要额外线性数组。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      每轮从未排序区间选择最小的元素,将其 放到已排序区间的末尾。 设数组的长度为 ,选择排序的算法流程如图11‑2 所示。 [0, − 1] [0, − 1] 1. 初始状态下,所有元素未排序,即未排序(索引)区间为 。 2

    参考来源

    - 位置:《Hello 算法--Go版本》第11章《排序》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/5.html;spine 4,归一字符[20307,20417)) - 结论依据:实际selectionSort边界j=i+1及不稳定图11-3支持。 - 原始内容:每轮从未排序区间选择最小的元素,将其 放到已排序区间的末尾。 设数组的长度为 ,选择排序的算法流程如图11‑2 所示。 [0, − 1] [0, − 1] 1. 初始状态下,所有元素未排序,即未排序(索引)区间为 。 2