为何Python中第三种Insertionsort实现速度远快于其他版本？

问题背景 #

三个实现均属于插入排序范畴，理论时间复杂度同为O(n²)，但在长度为10000的随机整数列表上测试时，性能差距达到两个数量级以上，测试输出结果如下：

Function finished in 2.2218 second(s)
Function finished in 3.4489 second(s)
Function finished in 0.0 second(s)

测试所用的排序实现与计时代码如下：

import time
import numpy as np

def insertionsort1(array):
    n = len(array)
    for i in range(n):
        index = 0
        while array[i] > array[index]:
            index +=1
        element = array.pop(i)
        array[index:index] = [element]
    return array


def insertionsort2(arr):
    n = len(arr)
    for i in range(1, n):
        for j in range(i):
            if arr[i] <= arr[j]:
                cache = arr.pop(i)
                arr[j:j] = [cache]
    return arr

def insertionsort3(arr):
    n = len(arr)
    for i in range(n-1):
        pos = i+1
        while pos > 0 and arr[pos] < arr[pos-1]:
            arr[pos], arr[pos-1] = arr[pos-1], arr[pos]
            pos -= 1
    return arr

def timeit(func, arr, n_runs):
    times = []
    for i in range(n_runs):
        start = time.time()
        _ = func(arr)
        end = time.time()
        times.append(end - start)
    avg_time = sum(times) / len(times)
    print(f'Function finished in {round(avg_time, 4)} second(s)')

array = list(np.random.randint(1, 10000, size=10000))
timeit(insertionsort1, array, 1)
timeit(insertionsort2, array, 1)
timeit(insertionsort3, array, 1)

性能差异核心原因 #

时间复杂度O(n²)仅描述算法操作次数随数据规模增长的量级，实际运行速度由单次操作的开销、实际执行的总操作次数共同决定，三个版本的性能差距来自三个核心层面：

• 前两个版本重度依赖高开销的列表动态操作
  Python列表是基于连续内存块实现的动态数组，非尾部位置的pop(i)、切片插入arr[a:a] = [x]操作，都需要把操作位置之后的所有元素整体挪动内存位置，单次操作耗时和列表长度正相关。前两个版本每次插入元素都要执行一次弹出+一次切片插入，等于在比较的O(n²)开销之外，又叠加了一层O(n²)的内存移动开销，常数项被拉得极高。第三个版本全程只做相邻元素的交换，单次交换仅涉及两个值的读写，没有整块内存挪动的额外成本，单次操作的开销比前两个版本低一到两个数量级。
• 前两个版本存在明显的逻辑冗余
  insertionsort1每次找插入位置都从列表头0索引开始遍历，完全没有利用插入排序“插入位左侧永远有序”的特性，做了大量重复比较；insertionsort2找到插入位置完成插入后没有终止内层j循环，插入操作已经改变了列表的索引映射，后续循环比较的已经不是最初要插入的元素，会产生大量无意义的比较甚至额外的重复操作。
• 测试代码的复用逻辑放大了性能差距
  计时逻辑每次都传入同一个原始列表对象，没有在单次测试后重置打乱数组。前两个函数执行完成后，列表已经被修改为有序状态，第三个函数实际处理的是完全有序的输入。插入排序在完全有序场景下仅需要O(n)次比较，不需要做任何交换操作，耗时极短，被四舍五入显示为0.0s。如果每次测试都传入重新打乱的同规模随机数组，第三个版本的实际耗时大概在2~3秒区间，依然比前两个版本快数倍，但不会出现0秒的极端结果。

内容的提问来源于stack exchange，提问作者moritz.burmester