在Python中测量快速排序和堆排序的时间

Question

我在用Python测量快速排序和堆排序的时间，但结果之间的差距太大了。请花点时间看看我的代码：

import time
import linecache
import random

def shell_sort(some_list):
    h=1
    while(h<=len(some_list)):
        h=3*h+1
    while h>0:
        for i in xrange(len(some_list)):
            j = i
            temp = some_list[i]
            while j >= h and some_list[j-h] > temp:
                some_list[j] = some_list[j - h]
                j -= h
            some_list[j] = temp
        h = h/3 if h/9 else (0 if h==1 else 1)
    some_list.reverse()

def quick_sort_r(some_list):
    l = []
    e = []
    g = []
    if len(some_list) <= 1:
        return some_list
    else:
        pivot = some_list[0]
        for x in some_list:
            if x < pivot:
                l.append(x)
            elif x > pivot:
                g.append(x)
            else:
                e.append(x)
        l = quick_sort_r(l)
        g = quick_sort_r(g)
        return g + e + l

def gen(number, b=100000):
    #return [random.randint(0, b) for x in xrange(number)]
    some_list = []
    return [some_list.append(random.randint(0, b)) for x in xrange(number)]

domain = [10000, 25000, 50000, 100000, 200000, 300000, 400000, 500000, 750000, 1000000]
for element in domain:
    print 'Results for: ' + str(element) + ' elements:'
    for j in range(0, 10):
        temp_list = gen(element)
        start = time.time()
        shell_sort(temp_list)
        end = time.time() - start
        print end
    print '*************************'

我在'gen'这个函数里用了两种代码。第一种是用堆排序，第二种是用快速排序。希望这个差距不会太大，这样是不对的。对于1000000个元素，快速排序大约需要0.5秒，而堆排序却需要23秒。到底出了什么问题呢？

提前谢谢你们。

Answer 1

这一行：

return [some_list.append(random.randint(0, b)) for x in xrange(number)]

... 是一个列表推导式，它生成了对 some_list.append(...) 的 number 次调用的结果，而这些调用的返回值都是 None：

>>> print gen(10)
[None, None, None, None, None, None, None, None, None, None]

None 的比较方式是这样的：

>>> None < None
False
>>> None > None
False

所以我想你们的排序可能会有点混乱。

快速排序之所以更快，是因为当列表里全是 None 时，它就变成了一个复制列表的函数：

def quick_sort_r(some_list):
    e = []
    if len(some_list) <= 1:
        return some_list
    else:
        pivot = some_list[0]
        for x in some_list:
            # all other comparisons are False
            e.append(x)

        return e

总之，建议使用 return [random.randint(0, b) for x in xrange(number)]。在我的电脑上，这个改动让快速排序的时间从 0.43 秒变成了 8.9 秒，这可能更符合你的预期。

顺便提一下，除非你的电脑很快，否则 Python 在处理 1,000,000 个数字的列表时表现得不太好 - 在我这台（有点慢的）电脑上，生成一百万个数字的列表大约需要 3 秒。