在最坏的情况下，插入排序和选择排序期间进行多少次比较？

Question

为了练习编码，我用Python编写了插入排序和选择排序。以下是插入排序：

def insertion(L, i):
    a = L[i + 1]
    for index in range(i + 1):
        if L[index] > a:
            break
    else:
        index = i + 1
    for k in range(i + 1, index, -1):
        L[k] = L[k - 1]
    L[index] = a
    return L
def insertion_sort(L):
    for i in range(len(L) - 1):
        L = insertion(L, i)
    return L

下面是选择的排序：

def selection_sort(L):
    for i in range(len(L) - 1):
        _min = i
        for j in range(i + 1, len(L)):
            if L[j] < L[_min]:
                _min = j
        L[_min], L[i] = L[i], L[_min]
    return L

然后，我使用N = 10000;L =i在范围(N，0，-1)中创建最坏的情况。在我看来，插入排序比选择排序快，因为选择的比较次数为49,995,000次，而插入次数仅为9999次。但当我用

import time
start = time.time()
……
end = time.time()

要测量时间，结果是插入排序比选择排序慢。我是否误解了比较的时代？

Answer 1

你确实漏掉了一些东西。即使您没有比较插入排序中的更多内容，也可以遍历列表并更改第二个for循环中的所有值，因为index =0是

在(N，0，-1)范围内的j= L=j，因此时间复杂度也是O(n^2)。与选择排序相同。

然而，我不明白为什么它需要更多的时间比选择排序。这可能是因为您正在调用inside (insertion_sort中的函数)，而且python使用的是额外的内存和时间。