排序算法最適合對排序數組進行排序

Question

當對已經排序的數組進行排序時，哪種排序算法最適合使用？

Answer 1

插入排序適用於幾乎排序的數據。您接近最佳結果。

這裏是一個偉大的動畫，顯示的排序將如何執行：http://www.sorting-algorithms.com/insertion-sort

Answer 2

這要看情況。數組的大小？ 「已經幾乎排序」是什麼意思 - 就像數據的百分比已經按順序排列了一樣？你的編程和數據存儲環境是什麼 - 內存中的數據，數據庫，文件？說了這麼多，你可以從研究Timsort開始。這是一種相對較新的排序算法，它將處理大型數據集，利用「運行」（數據已按排序順序排列）。

Answer 3

如果您將「幾乎排序」定義爲具有相反數量的數據點對，而不是正確的順序（例如，想象一下采取排序列表，然後採用不相交的連續數據點對並倒轉他們），那麼一個氣泡排序將工作得非常好，你做了一個修改，如果你交換兩個元素，那麼你繼續向左搜索並交換，只要相鄰元素失序。如果不成對的數量是O（n），則這將具有複雜度O（n）。