python - 关于排序算法效率的困惑

我在这本书上读过选择/插入/外壳排序算法，根据这本书，选择排序通常比插入排序慢，插入排序比外壳排序慢。然而，我使用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[:])

我的机器上的结果如下：

[linuxfish@Arch 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编写的

最佳答案

查看http://bigocheatsheet.com/排序部分而且http://en.wikipedia.org/wiki/Shellsort您使用的数据似乎会导致不同的行为，因为只有select sort是稳定的。
这是一个信息：

               | 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)

关于python - 关于排序算法效率的困惑，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25946616/