Python中最快的排序方法

Question

在Python中，怎样才能最快地对一个包含大于0且小于100000的整数的数组进行排序呢？不过，不要使用像sort这样的内置函数。

我在考虑根据输入的大小来结合使用两种排序方法。

Answer 1

早期的Python版本使用了一种混合排序算法，这种算法结合了samplesort（一种样本量较大的快速排序变种）和二进制插入排序。这个组合的效果有点不稳定。因此，从Python 2.3开始，Python就改用了adaptive mergesort（自适应归并排序）算法。

归并排序的平均时间复杂度是O(nlogn)，最坏情况下也是O(nlogn)。而快速排序在最坏情况下的时间复杂度是n*2。

如果你使用list=[ .............. ]这样的列表，

那么list.sort()会使用mergesort algorithm.（归并排序算法）来进行排序。

如果你想了解不同排序算法之间的比较，可以查看维基百科上的相关内容。

想要更详细的比较，可以访问这个链接。

Answer 2

因为你已经知道了数字的范围，所以可以使用一种叫做计数排序的方法，这种方法的时间复杂度是线性的，也就是说它的运行速度会比较快。

Answer 3

如果你对渐进时间感兴趣，那么计数排序或基数排序的表现都不错。

不过，如果你关心的是实际运行时间，那么你需要用你自己的数据集来比较不同算法的表现，因为不同的算法在处理不同的数据时效果会有所不同。在这种情况下，尝试快速排序总是值得的：

def qsort(inlist):
    if inlist == []: 
        return []
    else:
        pivot = inlist[0]
        lesser = qsort([x for x in inlist[1:] if x < pivot])
        greater = qsort([x for x in inlist[1:] if x >= pivot])
        return lesser + [pivot] + greater

来源：http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Python