用Python排序的最快方法

Question

在Python中对大于0且小于100000的整数数组进行排序的最快方法是什么？但不使用像sort这样的内置函数.

我正在考虑根据输入大小组合2种运动功能的可能性.

Answer 1

如果您对渐近时间感兴趣,那么计算sort或radix排序可以提供良好的性能.

但是,如果您对挂钟时间感兴趣,则需要使用特定数据集比较不同算法之间的性能,因为不同的算法对不同的数据集执行不同的操作.在这种情况下,它总是值得尝试快速排序:

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

Answer 2

由于您知道数字范围,因此您可以使用计数排序,它将在时间上呈线性.