algorithm - 大多数排序列表的排序算法

Question

我正在处理文件中的整数列表。而且我必须使用排序算法按降序对它们进行分类。我熟悉一些排序算法的运行时间，并且我知道它们的使用是根据情况而定的。所以我的问题是：对于已经排序 90% 的任意大小的列表，最快的排序算法是什么？（在我的文件中，我有 10.000 个条目，但其中 9.500 个已经排序）。

谢谢，

Answer 1

为 Python 开发的Timsort算法（现在在 Java 中使用）具有优化以处理内置的部分排序的“运行”。

Answer 2

插入排序应该没问题，如果您选择自己编写代码而不是使用语言提供的排序功能。

1. 当列表几乎排序时它表现得非常好（虽然它是O（N ^ 2）的顺序，如果列表几乎排序，内部循环将不会经常执行）
2. 这很容易实现。

介绍插入排序的 Python 实现。

程序

def InsertionSort(Array):
    Total = 0
    for i in xrange(1, len(Array)):
        j, I, = i - 1, i
        while j >= 0 and Array[I] > Array[j]:
            Array[I], Array[j] = Array[j], Array[I]
            j, I, Total = j - 1, I - 1, Total + 1
    print "Insertion Sort Total Operations :", Total

输出

最坏的情况下

TestArray  = range(1, 11)
InsertionSort(TestArray)
Insertion Sort Total Operations : 45

最佳案例

TestArray  = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
InsertionSort(TestArray)
Insertion Sort Total Operations : 0

90% 排序数组

TestArray  = [1, 9, 8, 7, 6, 5, 4, 3, 2, 10]
InsertionSort(TestArray)
Insertion Sort Total Operations : 17

半排序数组

TestArray  = [10, 9, 8, 7, 6, 1, 2, 3, 4, 5]
InsertionSort(TestArray)
Insertion Sort Total Operations : 10

Answer 3

对于它的 std::sort C++ 使用内省排序，其中数组/列表首先使用quicksort进行一定深度的递归排序，然后是heapsort。我不知道大约 90%，但 heapsort 似乎在已经排序的数组/列表上表现良好......所以我建议你尝试一下。