知识卡片
选择最小项扩张有序前缀
选择排序每轮扫描尚未排序的后缀,记录最小值位置,与后缀首位交换,使有序前缀增加一项。即使输入原已排序,仍按相同边界完成候选比较。
比较总数为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