我已經閱讀了關於選擇/插入/ shell排序算法的書,並且根據這本書,一般來說,選擇排序比插入排序慢,比shell排序慢。不過,我只用Python進行了一些測試,發現選擇排序是最快的!我無法弄清楚爲什麼,我能想到的唯一原因是列表中的元素之間有太多的交換。關於排序算法的效率的困惑
下面是我用於測試的代碼:
import random
import time
lst = [ random.randint(1,10000) for _ in xrange(10000) ]
def timeit(f):
def wrapper(*args):
t1 = time.time()
result = f(*args)
t2 = time.time()
print 'time: %f' %(t2 - t1)
return result
return wrapper
@timeit
def selectionSort(lst):
for i in xrange(len(lst)):
minNum = lst[i]
for j in xrange(i+1, len(lst)):
if lst[j] < minNum:
minNum = lst[j]
lst[i], minNum = minNum, lst[i]
return lst
@timeit
def insertionSort(lst):
for i in xrange(len(lst)):
for j in xrange(i, 0, -1):
if lst[j] < lst[j-1]:
lst[j], lst[j-1] = lst[j-1], lst[j]
else:
break
return lst
@timeit
def shellSort(lst):
h = 1
while (h < len(lst)//3):
h = h * 3 + 1
while (h >= 1):
for i in xrange(h, len(lst)):
for j in xrange(i, h-1, -h):
if lst[j] < lst[j-h]:
lst[j], lst[j-h] = lst[j-h], lst[j]
else:
break
h //= 3
return lst
selectionSort(lst[:])
insertionSort(lst[:])
shellSort(lst[:])
我的機器上的結果如下:
[[email protected] week2]$./sortAlgorithms.py
time: 4.533489
time: 22.247762
time: 12.867564
這是結果後,我已經添加了兩行代碼,漂亮令人驚歎......
time: 4.937693
time: 16.773167
time: 0.179526
分選方法改編自Robert Sedgewick的this book,我認爲我實現了與本書所說的算法完全相同的算法,儘管本書中的原始算法是用Java編寫的
你應該使用''//如果你想整數除法。這樣,即使在python3下或使用'from __future__ import division'時,表達式也會正確運行。 (除了使意圖更清楚)。 – Bakuriu 2014-09-20 08:11:13
@Bakuriu感謝您指出這一點!關於這個問題的任何見解? – linuxfish 2014-09-20 08:25:56
我不確定你爲什麼得到這個結果,但你可能想要檢查每次交換操作所消耗的時間。請注意,選擇排序所需的交換次數僅爲O(N),而不是O(N^2)。 – 2014-09-20 08:32:23