Python实现归并排序遇索引越界及timeit相关错误求助

1. 修复Merge函数的索引越界错误 #

你的merge函数初始化了空列表S = []后直接用S[k] = ...赋值，这会触发索引越界——空列表没有可访问的下标。正确做法是用append()添加元素，或是预先分配对应长度的列表：

修复后的merge函数（简洁版）： #

def merge(S1, S2):
    i = j = 0
    S = []
    while i < len(S1) and j < len(S2):
         if S1[i] < S2[j]:
             S.append(S1[i])
             i += 1
         else:
             S.append(S2[j])
             j += 1
    # 追加剩余未处理的元素
    S.extend(S1[i:])
    S.extend(S2[j:])          
    return S

预先分配空间版（更高效）： #

def merge(S1, S2):
    i = j = 0
    len1, len2 = len(S1), len(S2)
    S = [0] * (len1 + len2)
    while i < len1 and j < len2:
        if S1[i] < S2[j]:
            S[i+j] = S1[i]
            i += 1
        else:
            S[i+j] = S2[j]
            j += 1
    # 处理剩余元素
    while i < len1:
        S[i+j] = S1[i]
        i += 1
    while j < len2:
        S[i+j] = S2[j]
        j += 1
    return S

2. 修复numpy数组与Python列表的类型冲突 #

代码混合使用numpy数组和Python列表，导致递归时类型不兼容：

• mergesort里用S.size（numpy数组属性），但merge返回的是Python列表，列表没有size属性，会触发新错误。
• 统一用Python列表避免混乱：

修改测试数据生成代码： #

# 生成纯Python随机列表，避免内存溢出，调整长度范围到10^1到10^6
d = [random.sample(range(10**6), 10**i) for i in range(1, 7)]

修改mergesort的长度获取方式： #

def mergesort(S):
    n = len(S)  # 用len()适配列表
    if n <= 1:
        return S
    else:
        S1, S2 = split(S)
        S1sorted = mergesort(S1)
        S2sorted = mergesort(S2)
        Ssorted = merge(S1sorted, S2sorted)
        return Ssorted

3. 修复timeit计时逻辑错误 #

timeit的setup无法正确获取循环变量s，改用lambda包装排序操作，同时复制列表保证每次输入都是未排序状态：

修改计时代码： #

for s in d:
    # 复制列表避免原列表被排序后影响后续计时
    execution_time = timeit.timeit(stmt=lambda: mergesort(s.copy()), number=5)
    time_list.append(execution_time)
    length_list.append(len(s))
    print(f"列表长度: {len(s)}, 平均执行时间: {execution_time/5:.6f}秒")

4. 优化绘图以直观展示时间复杂度 #

添加O(N)、O(N²)和O(NlogN)的参考曲线，并用对数坐标放大趋势差异：

plt.scatter(length_list, time_list, label='归并排序实际耗时')
n_array = np.array(length_list)
# 计算系数让参考曲线与实际耗时匹配
coeff_n = time_list[-1] / n_array[-1]
coeff_n2 = time_list[-1] / (n_array[-1]**2)
coeff_nlogn = time_list[-1] / (n_array[-1] * np.log2(n_array[-1]))

plt.plot(n_array, coeff_n * n_array, label='O(N)', linestyle='--', color='red')
plt.plot(n_array, coeff_n2 * n_array**2, label='O(N²)', linestyle='--', color='green')
plt.plot(n_array, coeff_nlogn * n_array * np.log2(n_array), label='O(NlogN)', linestyle='--', color='orange')

plt.xlabel("列表长度N")
plt.ylabel("执行时间(秒)")
plt.legend()
plt.xscale('log')
plt.yscale('log')
plt.show()

完整修复后代码 #

import random
import timeit
import matplotlib.pyplot as plt
import numpy as np

def mergesort(S):
    n = len(S)
    if n <= 1:
        return S
    else:
        S1, S2 = split(S)
        S1sorted = mergesort(S1)
        S2sorted = mergesort(S2)
        Ssorted = merge(S1sorted, S2sorted)
        return Ssorted

def split(S):
    l = len(S)//2
    S1 = S[:l]
    S2 = S[l:]
    return S1, S2

def merge(S1, S2):
    i = j = 0
    S = []
    while i < len(S1) and j < len(S2):
         if S1[i] < S2[j]:
             S.append(S1[i])
             i += 1
         else:
             S.append(S2[j])
             j += 1
    S.extend(S1[i:])
    S.extend(S2[j:])          
    return S

if __name__ == '__main__':
    random.seed(5)
    d = [random.sample(range(10**6), 10**i) for i in range(1, 7)]
    time_list = []
    length_list = []
    for s in d:
        execution_time = timeit.timeit(stmt=lambda: mergesort(s.copy()), number=5)
        time_list.append(execution_time)
        length_list.append(len(s))
        print(f"列表长度: {len(s)}, 平均执行时间: {execution_time/5:.6f}秒")

    plt.scatter(length_list, time_list, label='归并排序实际耗时')
    n_array = np.array(length_list)
    coeff_n = time_list[-1] / n_array[-1]
    coeff_n2 = time_list[-1] / (n_array[-1]**2)
    coeff_nlogn = time_list[-1] / (n_array[-1] * np.log2(n_array[-1]))
    
    plt.plot(n_array, coeff_n * n_array, label='O(N)', linestyle='--', color='red')
    plt.plot(n_array, coeff_n2 * n_array**2, label='O(N²)', linestyle='--', color='green')
    plt.plot(n_array, coeff_nlogn * n_array * np.log2(n_array), label='O(NlogN)', linestyle='--', color='orange')

    plt.xlabel("列表长度N")
    plt.ylabel("执行时间(秒)")
    plt.legend()
    plt.xscale('log')
    plt.yscale('log')
    plt.show()

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