您將使用什麼排序算法對大型，幾乎排序的列表進行排序

Question

假設您擁有一個幾乎排序了30億個整數的數組。
哪種排序算法更適合（來自「經典」算法之一）？
如果列表完全是隨機的，那麼如何？

Answer 1

根據'算法簡介'的作者們對不同用法的排序方法進行了比較，您的標準將有利於InsertionSort。看到;

http://my.safaribooksonline.com/book/software-engineering-and-development/algorithms/9780596516246/sorting-algorithms/criteria_for_choosing_a_sorting_algorit

Answer 2

我會對兩者都使用合併排序，因爲它是在標準的unix sort（）調用中使用的，並且你沒有提供任何會改變它的約束（如最小時間或最小內存）。

Answer 3

考慮使用插入排序，如果輸入（幾乎）排序，則需要線性時間。即使輸入已排序，快速排序和合並排序的時間複雜度爲O（n log n）。