關於排序算法的效率的困惑

我已經閱讀了關於選擇/插入/ 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編寫的

來源

2014-09-20 linuxfish

你應該使用''//如果你想整數除法。這樣，即使在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

查看http://bigocheatsheet.com/排序部分。和http://en.wikipedia.org/wiki/Shellsort看來你使用的數據會導致不同的行爲，因爲只有選擇排序是穩定的。

這裏是一個的信息：

   | Best | Average | Worst 
Select Sort | O(n^2) | O(n^2) | O(n^2) 

Insertion Sort | O(n) | O(n^2) | O(n^2) 

Shell sort  | O(nlogn) | depends on the gap | O(n^2)

來源

2014-12-29 21:15:56 rpet

雖然這個鏈接可能回答這個問題，但最好在這裏包含答案的重要部分，並提供供參考的鏈接。如果鏈接頁面更改，則僅鏈接答案可能會失效。 – NKN 2014-12-30 00:05:11

@NKN鏈接不回答問題。 – OJFord 2015-01-09 23:21:55

關於排序算法的效率的困惑

回答

相關問題