高效排序

Question

我有一个值的数组，它几乎是排序的，但不是完全排序的，有几个值被移位了(比如，100000个值中有50个)。如何最有效地对其进行排序？

Answer 1

在假定数组几乎已排序的情况下，您可以使用以下方法之一：

Smoothsort

Wiki甚至有一个java实现。因为你不能比O(n)更快(因为为了找出一个数组是否排序都需要那么多时间)，平滑排序是一个很好的选择。更多细节here。

平滑排序的优点是，如果输入已经排序到一定程度，它将接近O(n)时间

Coctail sort

对于最坏情况和平均情况，大O记法中的鸡尾酒排序的复杂度都是O(n2)，但是如果在应用排序算法之前列表主要是排序的，则它变得更接近O(n)，

Timsort

java的数组实际上在java7中使用timsort来对对象进行排序(sort())。timsort here的描述。

Answer 2

使用insertion sort；这对于几乎排序的数组来说非常好，因为它们的时间接近O(n)。实际上，我相信.NET框架使用插入排序在内部对枚举值进行排序(因为它们通常是排序的)，尽管我必须重新检查这一点。

Answer 3

我的第一个直觉是识别放错位置的元素，并将它们移动到一个单独的数组中，使用您喜欢的任何算法对它们进行排序(对于这几个算法，这并不重要)，然后对它们进行合并排序。