知识卡片

普通读书笔记卡 · 5654.c.1.a.2.a.2.a.18 · 生成模型:未记录

选择排序减少交换但仍需比较

理解等级:中级

每轮在线性扫描中选出未排序区间的最大值,再把它交换到区间末端。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语言实现 选择排序在本章描述的算法中是最慢的,即使在最好情况下(如数组已经有序)它都需要二次方时间。它重复地进行着几乎