直接用timeit单次调用测排序结果不准，因未预热、输入复用、忽略数据分布及系统噪声；正确做法是用repeat取最小值、每次生成新列表、统一随机种子，并分随机/逆序/已排序三类场景测试。
直接用 timeit 测排序算法，结果大概率不准——默认只跑一次、没预热、忽略输入规模变化，还可能被 Python 的小整数缓存或列表复用干扰。
为什么不能直接用 timeit.timeit() 单次调用测排序
常见错误是这样写：timeit.timeit("sorted(arr)", setup="arr = list(range(1000, 0, -1))", number=1)。这会严重低估真实耗时，因为：
-
setup中的arr在每次重复执行时不会重新生成，第二次起实际测的是已排好序的列表（sorted()对有序输入有优化） -
number=1太小，系统噪声占比高；而默认number=1000000又会让慢算法（如冒泡）卡死或溢出 - 没控制输入特征：随机、逆序、近似有序等不同分布对快排、归并、Timsort 影响极大
正确构造可比基准测试的三个关键动作
必须让每次计时都基于“全新、可控、一致”的输入：
- 用
lambda包裹排序调用，并在内部生成新列表：lambda: sorted(list(range(1000, 0, -1)))，避免变量复用 - 用
timeit.repeat(repeat=3, number=1000)替代单次timeit()，取最小值（排除 GC 或系统抖动干扰） - 对每种算法，统一用相同种子生成随机数据：
random.seed(42); arr = [random.randint(1, 1000) for _ in range(1000)]，再传入setup或闭包
实测中必须区分的三类输入场景
同一算法在不同数据下性能可能差 10 倍以上：
立即学习“Python免费学习笔记（深入）”；
-
随机数据：用
random.shuffle()打乱list(range(n))，适合对比平均情况 -
逆序数据：直接
list(range(n, 0, -1))，暴露快排最坏 O(n²) 行为 -
已排序数据：原生
list(range(n))，Timsort 会秒出，但插入排序也极快——此时比的是“适应性”而非绝对速度
例如测 sorted() 和手写快排时，若只用随机数据，会误判后者更快；加上逆序输入，立刻暴露递归深度和切片开销问题。
绕不开的底层细节：为什么 sorted() 总是赢家
Python 内置 sorted() 是 Timsort，它不是“一种算法”，而是根据输入动态组合插入+归并的策略：
- 对长度
- 检测已排序段（run），合并时跳过冗余比较
- C 实现，无解释器开销；而纯 Python 快排/归并哪怕逻辑最优，也逃不开对象创建和属性查找成本
所以实测时如果发现自定义算法比 sorted() 快，第一反应应是检查是否误测了空列表、小数组或重复引用——真正的大规模、混合分布数据下，几乎不可能胜出。
真正需要自己实现排序的场景极少，更多是理解分治边界、稳定性取舍或内存约束；一旦进入实测环节，数据生成方式和重复策略比算法本身更容易成为瓶颈根源。
