的選擇排序比插入大數組要快嗎？

Question

可能重複：
Efficency of Insertion Sort vs Bubble sort vs Selection sort?

是選擇排序比插入的大陣列更快？當它在最壞的情況下呢？

我知道插入比選擇更快，但對於大型數組和最差情況？

Answer 1

所涉及的數組的大小很少有很大的後果。

真正的問題是比較與複製的速度。選擇排序將勝出的時間是比複製快批次。舉例來說，讓我們假設兩個字段：一個int作爲一個鍵，另一個數據附加到它。

在這種情況下，比較只涉及單個int，所以它非常快，但複製涉及整個兆字節，所以它幾乎肯定會慢很多。

由於選擇排序進行了大量比較，但相對較少的副本，這種情況會有利於它。插入排序做了更多的副本，所以在這種情況下，較慢的副本會使其速度變慢。

就選擇排序的最壞情況而言，它幾乎相反 - 任何情況下複製速度都很快，但比較速度很慢。

Answer 2

插入排序，如果執行得好，使用memcpy（）來移動其他值。所以它取決於處理器，緩存速度（第一級第二級chache），緩存大小，當一個算法變得比另一個快時。

我記得一個實現（是java？），其中一個算法被使用時，元素的數量沒有超過特定的硬編碼閾值，否則使用另一個算法。

所以，你只需要測量它。 大O表示法對於中小型數組有點誤導，那麼O（N）表示c * O（N）。 因子c影響總執行時間。

Answer 3

按照Wikipedia article，

一般來說，插入排序將寫入存儲陣列O（N 2）次，而 選擇排序將只寫爲O（n）次。由於這個原因， 選擇排序可能更適用於寫入存儲器的情況比讀數貴得多，例如EEPROM或 閃存。

無論數組大小如何，情況都是如此。事實上，隨着陣列變大，差異會更加明顯。