algorithm - 选择排序比插入大数组更快吗？

Question

可能的重复：
插入排序与冒泡排序与选择排序的效率？

选择排序比插入大数组更快吗？最坏的情况是什么时候？

我知道插入比选择快，但是对于大型数组和最坏的情况？

Answer 1

所涉及的数组的大小很少有很大的影响。

真正的问题是比较与复制的速度。选择排序获胜的时间是比较比复制快得多。举个例子，让我们假设两个字段：一个 int 作为键，另外一个兆字节的数据附加到它上面。

在这种情况下，比较只涉及单个 int，因此速度非常快，但复制涉及整个兆字节，因此几乎可以肯定会慢一些。

由于选择排序做了很多比较，但比较少的副本，这种情况将有利于它。插入排序会做更多的副本，所以在这种情况下，较慢的副本会减慢它的速度。

就选择排序的最坏情况而言，情况恰恰相反——复制速度很快，但比较速度很慢。

Answer 2

根据维基百科的文章，

一般来说，插入排序会写入数组 O(n2) 次，而选择排序只会写入 O(n) 次。由于这个原因，在写入存储器比读取更昂贵的情况下，例如使用 EEPROM 或闪存，选择排序可能更可取。

无论数组大小如何，这都是正确的。事实上，随着数组变大，差异会更加明显。

Answer 3

插入排序，如果实施得当，使用 memcpy() 移动其他值。所以它取决于处理器、缓存速度（第一级第二级缓存）、缓存大小，当一个算法变得比另一个更快时。

我记得一个实现（是 java 吗？）当元素的数量不超过特定的硬编码阈值时使用一个算法，否则使用另一个算法。

所以，你只需要测量它。大 O 表示法对于中小型数组有点误导，那么 O(N) 表示 c * O(N)。因素 c 影响总执行时间。