import time import bisect,heapq,random def sort1(n): "sort1 : bisect" lst = [] for i in xrange(n): bisect.insort_left(lst,random.randint(1,10000)) return lst def sort2(n): "sort2 :lst.sort" lst = [] for i in xrange(n): lst.append(random.randint(1,10000)) lst.sort() return lst def sort3(n): "sort3 : heapq" lst = [] for i in xrange(n): heapq.heappush(lst,random.randint(1,10000)) return lst for i in [sort1,sort2,sort3]: time1 = time.clock() i(100000) time2 = time.clock() time_all = time2-time1 print i.__doc__,time_all输出结果:
sort1 : bisect 2.49 sort2 :lst.sort 0.36 sort3 : heapq 0.42为什么bisect, heapq反而比内置方法 sort 还要慢？
1.
bisect根据
insort_left的文档：也就是说，单次
insort_left的时间复杂度是O(n)，自然sort1的复杂度就变成了O(n^2)，它最慢是应当的。2.
sort文档说是
O(n log n)的复杂度。从 listsort 详细文档来看，开发人员着实没少下了工夫。3.
heappush根据维基百科，插入操作的时间复杂度是
O(log n)，所以总的时间复杂度仍然是O(n log n)。不过有一点值得注意，插入操作的平均时间是O(1)，所以有可能会稍微快一点。Python vs. PyPy
CPython 2.7
PyPy 2.4
注，我把你的调用部分复制了一遍，执行了两次，结果为第二次的输出。
可以看得出，
O(n log n)算法的耗时是在同一个数量级上的，但 CPython 中sort胜出，PyPy 中heapq胜出。cProfile
用
cProfile来测试，先看一下 CPython 的结果：CPython
lst.sort:CPython
heapq:可以看出，相同操作消耗的时间差不太多，不同的地方在于
sort用了62ms、append用了71ms，总共是133ms；而相比之下，heappush用了210ms。再根据之前 PyPy 的迹象，这里怀疑 CPython 和heapq的 C 实现在多次互相调用中有一些解释器相关的“额外”代码。最后再看一下 PyPy 的情况。
PyPy
lst.sort:PyPy
heapq:情况发生了变化！PyPy 的
heapq实现是纯 Python 的，依托 PyPy 的性能来达到飞一般的效果。不过，在增加了cProfile的钩子之后，大量的函数调用计数变成了瓶颈，增加了heapq算法的时间消耗。总结
n^2的算法毋庸置疑最慢，但同样是n log n，依次插入方式的堆排序可能会比内置的sort函数稍快一些，但因为 CPython 本身的一些限制无法体现。