冒泡、选择、插入三种排序算法比较

虽然冒泡、选择、插入三种排序算法的时间复杂度是n2，但是他们之间也还是有差距的，下面通过几组数据对比

对比代码实现

import random
import time
import copy

def cal_time(func):
    def wrapper(*args,**kwargs):
        t1=time.time()
        result=func(*args,**kwargs)
        t2=time.time()
        print(f"{func.__name__} 耗时 {t2-t1} 秒")
        return result
    return wrapper

@cal_time
def insert_sort(li):
    for i in range(1,len(li)):
        for j in range(i,0,-1):
            if li[j]<li[j-1]:
                li[j],li[j-1]=li[j-1],li[j]
            else:
                break
    return li

@cal_time
def select_sort(li):
    for i in range(len(li)-1):
        index=i
        for j in range(i+1,len(li)):
            if li[j]<li[index]:
                index=j
        if i!=index:
            li[i],li[index]=li[index],li[i]
    return li

@cal_time
def bubble_sort(li):
    has_exchange=False
    for i in range(len(li)-1):
        for j in range(len(li)-i-1):
            if li[j]>li[j+1]:
                has_exchange=True
                li[j],li[j+1]=li[j+1],li[j]
        if not has_exchange:
            break
    return li

if __name__=="__main__":
    num=10000
    li=[random.randint(0,10000000) for r in range(num)]
    li2=copy.deepcopy(li)
    li3=copy.deepcopy(li)
    bubble_sort(li)
    insert_sort(li2)
    select_sort(li3)

准备对比数据

（1）采用 100000，10000，1000三组随机整数列表进行对比，即将上述代码中num分别设置为这三个数，对比结果如下：

排序算法	1000	10000	100000
冒泡排序	0.039486	4.528	514.022
插入排序	0.026380	2.869	406.644
选择排序	0.016201	1.723	211.193

(2)采用10000个随机数据，进行10轮排序观察结果如下：

排序算法	1	2	3	4	5	6	7	8	9	10
冒泡排序	4.418	4.444	4.597	4.506	4.500	4.605	4.806	4.631	4.511	4.438
插入排序	2.972	2.868	2.795	2.890	2.864	2.949	2.957	2.826	2.916	2.954
选择排序	1.770	1.688	1.633	1.583	1.616	1.594	1.630	1.614	1.647	1.702

(3)使用最坏的情况

测试代码：

if __name__=="__main__":
    li=[elem for elem in range(10000,-1,-1)]
    li2=copy.deepcopy(li)
    li3=copy.deepcopy(li)
    bubble_sort(li)
    insert_sort(li2)
    select_sort(li3)

执行结果：

bubble_sort 耗时 5.654977798461914 秒
insert_sort 耗时 5.424242973327637 秒
select_sort 耗时 1.8394582271575928 秒

冒泡、插入、选择三种排序算法对比结论

• 冒泡排序算法是最慢的，其次是插入排序，选择排序算法是最快的
• 在最坏的情况下，选择排序仍然是最快的，而且要远快于冒泡和插入排序
• 在最快的情况下，冒泡和选择耗时接近
• 选择排序之所以能做到远比冒泡排序和插入排序快，其原因在于选择排序交换数据的次数更少