最坏情况下插入排序与选择排序的比较次数及运行效率疑问

1. 最坏情况的比较次数 #

• 选择排序：无论输入序列顺序，比较次数固定为 N*(N-1)/2，当N=10000时，就是49995000次，你的计算是正确的。
• 插入排序：你搞混了最好情况和最坏情况的比较次数。插入排序最好情况（输入已升序）的比较次数是 N-1，也就是你以为的9999次，但你构造的倒序序列是插入排序的最坏情况，每一轮插入都需要和前面所有已排序元素比较，总比较次数同样是 N*(N-1)/2，和选择排序量级一致。

2. 插入排序运行更慢的原因 #

两者最坏情况比较次数相当，但操作开销差异很大：

• 插入排序最坏情况下，除了比较操作，还需要做大量元素移动操作，总移动次数也是 N*(N-1)/2，对应5000万次左右的列表赋值操作，开销极高。
• 选择排序每一轮遍历仅需要做1次元素交换，总交换次数为 N-1，仅9999次列表赋值操作，这部分开销远小于插入排序。

代码实现 #

插入排序 #

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 for i in range(N, 0, -1)]
计时逻辑：

import time
start = time.time()
# 执行排序代码
end = time.time()

内容的提问来源于stack exchange，提问作者Shizumu