知识卡片
选择排序减少交换但仍需比较
每轮在线性扫描中选出未排序区间的最大值,再把它交换到区间末端。n 个元素固定比较 n(n−1)/2 次,即使输入已有序也如此;交换次数至多 n−1,通常为 O(n),相比比较次数更少。
跨位置交换可能改变相等元素之间的先后次序,因此该实现不稳定。它有时适合写入比比较更昂贵的小规模场景,但是否有利仍需评估。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
选择排序 给你一堆标上数字的牌,一个通常的排序方法是选择并且拿走最大的牌,然后重复这个过程直到所有的牌都被拿走。这个方法描述了选择排序的过程,如例4-8所示。 例4-8:选择排序的C语言实现 选择排序在本章描述的算法中是最慢的,即使在最好情况下(如数组已经有序)它都需要二次方时间。它重复地进行着几乎
参考来源
- 位置:《算法技术手册》第4章《选择排序》(spine1512;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1475.html;u085-ch04-019)。
- 结论依据:85全文及03210完整C实现实读;比较与交换次数为推导。
- 原始内容:选择排序 给你一堆标上数字的牌,一个通常的排序方法是选择并且拿走最大的牌,然后重复这个过程直到所有的牌都被拿走。这个方法描述了选择排序的过程,如例4-8所示。 例4-8:选择排序的C语言实现 选择排序在本章描述的算法中是最慢的,即使在最好情况下(如数组已经有序)它都需要二次方时间。它重复地进行着几乎