我正在用Python测量Quick and Heap排序的时间,但是结果之间的差异太大。请花一点时间看一下我的代码:
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个元素的QS约为0.5 s,HS为23 s。怎么了?
感谢前进。
这行:
return [some_list.append(random.randint(0, b)) for x in xrange(number)]
...是一个列表推导,生成对的number
调用结果some_list.append(...)
,所有这些都返回None
:
>>> print gen(10)
[None, None, None, None, None, None, None, None, None, None]
None
比较如下:
>>> None < None
False
>>> None > None
False
因此,我想您的两种选择都相当混乱。
快速排序更快,因为有了None
s列表,它就变成了复制列表的函数:
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.43s提升到8.9s,这可能比您期望的要多。
顺便说一句,除非您拥有一台快速的机器,否则Python不会很好地同意1,000,000个数字的列表-我的计算机(有些慢)大约需要3秒才能生成100万个数字的列表。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句