python - 与其他排序算法相比，为什么插入排序如此之快？

Question

我一直在测试各种其他排序算法(Selection、Quick、Bubble、Shell、Radix 等)以及插入排序的速度。然而，插入排序似乎是迄今为止最快的算法。我一直认为快速排序是最快的。

这是我在 Python 3 中的插入排序和计时器函数的代码。

def InsertionSort(argShuffledList):
    for index in range(1,len(argShuffledList)):

        currentvalue = argShuffledList[index]
        position = index

        while position>0 and argShuffledList[position-1]>currentvalue:
            argShuffledList[position]=argShuffledList[position-1]
            position = position-1

        argShuffledList[position]=currentvalue
    return argShuffledList

def Timer(argFunction, *args): ## function for timing functions
    dblStart = time.clock()
    argFunction(*args)
    intTime = "%.2f" % ((time.clock() - dblStart) * 1000000)
    message = "Elasped Time: " + str(intTime) + " microseconds"
    return message

insertionSortList = InsertionSort(insertionCopyList) 
timeInsertionSortList = Timer(InsertionSort, insertionCopyList)

Answer 1

您在对列表进行计时之前对其进行排序。所以当你计时时，列表已经排序，你的插入排序不需要做任何插入，所以在线性时间内运行。

insertionSortList = InsertionSort(insertionCopyList) 
timeInsertionSortList = Timer(InsertionSort, insertionCopyList)

不清楚第一次调用 InsertionSort 的意图是什么，除非您正在尝试对已经排序的列表计时。