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

Question

假设您有一个几乎已排序的 30 亿个整数数组。
哪种排序算法更合适（从“经典”算法中）？
如果列表是完全随机的呢？

score 1 · Accepted Answer

我会对两者都使用合并排序，因为它是标准 unix sort() 调用中使用的，并且您没有提供任何会改变它的约束（例如最小时间或最小内存）。

score 1 · Accepted Answer

考虑使用插入排序，如果输入（几乎）已排序，则需要线性时间。即使输入已排序，快速排序和归并排序的时间复杂度也为 O(n log n)。

score 1 · Accepted Answer

根据“简而言之算法”的作者，他们比较了不同用途的排序方法，您的标准将支持 InsertionSort。看;

3 回答 3