排序 - 选择排序如何有效？

2 回答

• 3

  我认为你过分夸大了作者的主张 .

  在谈到相对效率时，本书的作者在非常具体的情况下比较算法：

  • 他比较了他具体实施的时间，

  • 他比较了他特定硬件的时间

  • 他比较了随机数据集的时间（与动画页面相对，后者提供了四种选择）

  通过测量在这些特定情况下的时间，作者得出的结论是，当在他的特定硬件上对10,000个随机播种的元素进行排序时，他在三种实现中的选择排序的实现是最快的 . 这是他可以合理地提出的唯一主张 . 特别是，对于作者的实验来说，选择排序在某种程度上是三者中效率最高的主张太过笼统 .

  作者的实验导致他所展示的排名的原因很可能是算法的缓存友好性 .

  选择排序大多数时间在单个方向上读取，并且其大多数操作都是读取 . 另一方面，插入排序做了大量的写作 . 冒泡排序在大多数情况下也会出现相同的方向，但它会将写入与读取混合，并且写入比选择排序更多 . 简而言之，作者对选择排序的实现似乎是作者硬件的三种算法中最优化的

  回复于 2024-04-29T16:20:32+08:00
• 0

  我不认为选择排序是非常有效的排序算法，但它比冒泡排序有效，但我怀疑插入排序

  因为选择排序执行inplace排序，它从列表的其余部分中删除最小元素，然后将其插入到目前为止排序的值的末尾 .

  插入排序仅作为排序元素所需的元素进行扫描，但选择排序必须扫描整个列表以对任何元素进行排序 .

  有关选择排序，请参阅此示例

  64 25 12 22 11

  首先，它在此列表中找到最小元素，它是11

  现在交换11和64

  11 25 12 22 64

  接下来找到25 12 22 64的最小值，即12

  所以现在名单是11 12 25 22 64这个过程继续进行

  与插入排序一样的地方

  64 25 12 22 11

  它首先检查25小于64

  25 64 12 22 11

  12 64 25 22 11

  12 25 64 22 11

  12 22 64 25 11

  12 22 25 64 11

  11 22 25 64 12

  11 12 25 64 22

  11 12 22 64 25

  11 12 22 25 64

  气泡，选择和插入的时间复杂度为O（n2）

  选择排序适用于较小的列表但我认为它们对于大型列表失败，对于较大的列表，合并/快速排序是最好的

  希望这可以帮助

  回复于 2024-04-29T16:20:32+08:00