您会使用什么排序算法来对大的、几乎排序的列表进行排序

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)。