插入/选择排序步数更少却更慢？Python排序算法性能异常排查

我编写了一个对比冒泡排序（bubble sort）、插入排序（insertion sort）和选择排序（selection sort）的Python脚本。三者时间复杂度均为O(N²)，理论上选择排序的操作步数仅为冒泡排序的一半，应更快，但实际测试中选择排序和插入排序耗时远高于冒泡排序。我已确保每次调用算法时使用原数组的深拷贝，以下是我的代码、测试输出，请求排查实现错误或验证结果是否符合算法真实性能：

代码实现 #

#!/usr/bin/env python3
import random
import time
import copy 

# timer function for sorting algorithms 
def timeit(f):
    def wrapper(*args, **kwargs):
        st = time.time()
        y = f(*args,**kwargs)
        ft = time.time()
        print(f.__name__,'\n', ft-st, 'seconds')
        if y:
            print("verifying...")
            assert sorted(args[0]) == y, f'{f.__name__} did not sort the array correctly'
            print(f'{f.__name__} sorted correctly\n\n')
            return y
    return wrapper 


# function to sample unsorted array
def sample_array(n=10000, type=['unordered','ordered'][0]):
    if type == 'unordered':
        return list(random.choices(list(range(1,101)),k=n))
    if type == 'ordered':
        return sorted(list(random.choices(list(range(1,101)),k=n)))



@timeit 
def bubble_sort(arr, ascending=True):
    while True:
        swapped = False
        for idx in range(len(arr)):
            try:
                if arr[idx] > arr[idx+1]:
                    arr[idx+1] = arr[idx]
                    swapped = True
                elif arr[idx] <= arr[idx+1]:
                    pass
            except IndexError:
                pass
        if not swapped:
            return arr 
         

@timeit 
def selection_sort(arr):
    n = len(arr)
    for i in range(n-1):
        min_idx = i
        for j in range(i+1, n):
            if arr[min_idx] > arr[j]:
                min_idx = j
        if min_idx != i: 
            tmp = arr[i]
            arr[i] = arr[min_idx]
            arr[min_idx] = tmp 
    return arr 



# comparing to python's sort algorithm                 
@timeit
def python_sort(arr):
    return sorted(arr)



@timeit
def insertion_sort(arr):
    n = len(arr)

    for idx in range(1, n):
        temp =  arr[idx]
        pos = idx - 1
        while pos >= 0:
            if arr[pos] > temp:
                arr[pos+1] = arr[pos]
                pos -= 1
            else:
                break
        arr[pos+1] = temp 
        
    return arr



if __name__=="__main__":
    x = sample_array()
    for f in [bubble_sort,python_sort,selection_sort, insertion_sort]:
        xc = copy.deepcopy(x)
        f(xc)

测试输出 #

bubble_sort 
 0.0033044815063476562 seconds
verifying...
bubble_sort sorted correctly


python_sort 
 0.0008809566497802734 seconds
verifying...
python_sort sorted correctly


selection_sort 
 2.7145907878875732 seconds
verifying...
selection_sort sorted correctly


insertion_sort 
 3.0474853515625 seconds
verifying...
insertion_sort sorted correctly

疑问 #

• 为何选择排序和插入排序耗时远高于冒泡排序？
• 是否存在实现错误？
• 该结果是否符合算法真实性能？

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