问排序-如何选择排序是有效的？

EN

我认为你把作者的主张概括得太笼统了。

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

• 他比较了具体实现的时间，
• 他比较了他的具体硬件的时间。
• 他比较了随机数据集的时间(相对于动画页面，后者提供了四种选择)。

通过测量在这些特定情况下的时间，作者得出结论，当在他的具体硬件上对10,000个随机种子元素进行排序时，他的选择排序实现速度最快。这是他唯一能合理地提出的主张。特别是，对作者的实验来说，选择排序在某种程度上是最有效的一种说法太笼统了。

作者的实验结果显示出排名的原因很可能是算法对缓存的友好性。

选择排序大部分时间以单一方向读取，其大部分操作都是读的。插入排序，另一方面，做了大量的写作。大多数情况下，冒泡排序也是朝着相同的方向进行的，但是它将写和读混为一谈，并且比选择排序做得更多。总之，作者对选择排序的实现似乎是作者硬件三种算法中最优化的

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

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

插入排序只根据需要对元素进行扫描，但选择排序必须扫描整个列表才能对任何元素进行排序。

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

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)

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

希望这能有所帮助