插入排序反向數組選擇排序更快嗎？

Question

如果我們有一個反向排序的數組，是否選擇排序比插入排序快？

我覺得選擇排序更快，因爲我們有O(n^2)搜索和O(n)交換，但在插入排序我們有O(n^2)交換和O(n^2)搜索。

任何人都可以告訴我，如果我是正確的？ 謝謝

Answer 1

我已經在我自己的Python實現上對這個主題做了一些基準測試。它在很大程度上取決於你有什麼類型的輸入。我發現對於隨機排序的輸入，Insertion Sort稍快（如3％），但對於反向排序的輸入，Selection排序要快得多。我一直聽說Selection Selection是兩者中速度較快的，但是我自己的基準測試並沒有反映出這一點。