Python排序算法速度对比绘图程序运行异常求助

原代码的核心故障点 #

• 随机列表生成结果未被接收：调用create_list生成测试数组后，未将函数返回的列表赋值给变量，后续排序函数始终处理初始定义的空列表，完全无法获得有效计时数据
• 循环变量重名复用：三层嵌套循环全部使用i作为计数变量，代码可读性差，后续修改逻辑时极易出现计数错乱问题
• 全局变量耦合风险：所有排序函数依赖全局变量tidtog传递计时结果，代码复用过程中极易出现计时值被意外覆盖的问题
• 自定义函数参数失效：create_list定义的max参数未被实际使用，随机数范围硬编码为0-100，传入的参数完全不生效
• 绘图流程缺失：plot函数未调用plt.show()，就算完成所有数据绘制，也不会弹出图片窗口；同时未添加图例、网格，无法区分不同算法对应的曲线

可直接运行的修复版完整代码 #

import random
from time import perf_counter
import matplotlib.pyplot as plt

def create_list(n, max_val):
    # 生成指定长度、元素范围的随机测试列表
    return [random.randint(0, max_val) for _ in range(n)]


def find_lowest_value(start_pos, lista):
    # 从起始位置开始查找列表中最小值对应的索引
    lowest_value = lista[start_pos]
    lowest_value_pos = start_pos
    for i in range(start_pos + 1, len(lista)):
        if lowest_value > lista[i]:
            lowest_value_pos = i
            lowest_value = lista[i]
    return lowest_value_pos 

######################
# 排序算法实现（返回值包含排序结果、运行时长）
######################
def bubble_sort(lista):
    tidstart = perf_counter()
    bubble_lista = lista.copy()
    osorterad = True
    while osorterad:
        osorterad = False
        for i in range(len(bubble_lista) - 1):
            if bubble_lista[i] > bubble_lista[i+1]:
                bubble_lista[i], bubble_lista[i+1] = bubble_lista[i+1], bubble_lista[i]
                osorterad = True       
    tidstopp = perf_counter()
    run_time = round((tidstopp - tidstart) * 1000, 4)
    return bubble_lista, run_time

def selection_sort(lista):
    tidstart = perf_counter()
    selection_lista = lista.copy()
    for i in range(len(selection_lista) - 1):
        low_pos = find_lowest_value(i, selection_lista)
        if i != low_pos:
            selection_lista[i], selection_lista[low_pos] = selection_lista[low_pos], selection_lista[i]
    tidstopp = perf_counter()
    run_time = round((tidstopp - tidstart) * 1000, 4)
    return selection_lista, run_time

def insert_sort(lista):
    tidstart = perf_counter()
    insert_lista = lista.copy()
    for i in range(1, len(insert_lista)):
        nyckel = insert_lista[i]
        j = i - 1
        while j >= 0 and nyckel < insert_lista[j]:
            insert_lista[j + 1] = insert_lista[j] 
            j = j - 1 
        insert_lista[j + 1] = nyckel
    tidstopp = perf_counter()
    run_time = round((tidstopp - tidstart) * 1000, 4)
    return insert_lista, run_time

def python_sort(lista):
    tidstart = perf_counter()
    python_lista = sorted(lista)
    tidstopp = perf_counter()
    run_time = round((tidstopp - tidstart) * 1000, 4)
    return python_lista, run_time

##################
# 计时测试与绘图模块
#################
sim_range = 10  # 若程序运行过慢，可适当调小该值
repetitioner = 10
step_size = 1000

# 绑定排序函数与对应曲线名称
sort_functions = [
    (bubble_sort, "冒泡排序"),
    (selection_sort, "选择排序"),
    (insert_sort, "插入排序"),
    (python_sort, "Python内置sorted")
]

# 初始化存储横轴（列表长度）、纵轴（平均运行时间）的容器
x_all = []
y_all = []
for _ in sort_functions:
    x_all.append([])
    y_all.append([])

# 遍历所有排序算法，开展多轮计时测试
for func_idx, (sort_func, func_name) in enumerate(sort_functions):
    current_x = x_all[func_idx]
    current_y = y_all[func_idx]
    current_size = 0
    # 遍历不同长度的测试列表
    for size_idx in range(sim_range):
        current_size += step_size
        current_x.append(current_size)
        total_time = 0
        # 重复测试多轮取平均值，消除偶然误差
        for rep_idx in range(repetitioner):
            test_list = create_list(current_size, current_size)
            _, run_t = sort_func(test_list)
            total_time += run_t
        avg_time = total_time / repetitioner
        current_y.append(avg_time)

def plot():
    plt.xlabel("测试列表长度")
    plt.ylabel("平均运行时间（毫秒）")
    plt.grid(alpha=0.3)
    for func_idx, (_, func_name) in enumerate(sort_functions):
        plt.plot(x_all[func_idx], y_all[func_idx], label=func_name)
    plt.legend()
    plt.show()

plot()

使用提示 #

• 冒泡、选择、插入排序的时间复杂度为O(n²)，当测试列表长度超过10000后运行时间会快速上升，若觉得程序加载过慢，可适当调小sim_range或step_size参数
• 移除了原代码中每次排序时的多余打印语句，减少控制台输出对计时精度的干扰
• 所有排序函数不再依赖全局变量传递计时结果，后续扩展新排序算法时不会出现值被意外篡改的问题

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