algorithm - 最好的排序方法？

Question

问题；

You have to sort an array of bank transactions by date. Most of them are in order (by date), only a few are out of order.

Which sorting algorithm will you use between insertion sort, selection sort and merge sort in order to take advantage of the fact that the array is almost sorted?

我的回答(不确定是否正确)

假设 N >= 5，我会选择合并排序，因为它的平均值。时间复杂度为 O(n * log n)，这比插入排序 O(n^2) 更有效。然而，由于多个交易将在同一日期发生，插入排序将是一种很好的稳定排序方法。

在这种情况下，哪个更好？合并排序还是插入排序？我的方向正确吗？

Answer 1

您应该选择插入排序，不是因为稳定性，而是因为它具有自适应性(请参阅 here )并且由于输入几乎是从一开始就排序的事实而表现出色。

这个“自适应”特性的意思是，已经到位的元素在O(1)时间被处理，非常接近它们排序位置的元素也可以被认为是O(1)(最多一些k距离).