Python实现的选择排序为何远快于C++实现？求原因解析

哈哈，这个看起来离谱的结果其实是基准测试的输入数据被意外修改造成的假象，咱们一步步拆解问题：

1. 核心问题：Python测试用例的全局列表被修改，后续调用全是处理空列表 #

先看你的Python selection_sort 实现：

def selection_sort(arr: list) -> list:
    sorted_arr = []
    while len(arr) != 0:
        smallest_idx = find_smallest_element(arr)
        sorted_arr.append(arr.pop(smallest_idx))  # 这里会直接修改传入的原列表！
    return sorted_arr

而你的Python基准测试代码里，直接传入了全局的UNSORTED_LIST：

def test_selection_sort_benchmark(benchmark: BenchmarkFixture) -> None:
    benchmark.pedantic(
        target=selection_sort,
        args=(UNSORTED_LIST,),  # 直接传原列表，没有创建副本
        rounds=100,
        warmup_rounds=5,
        iterations=30,
    )

第一次调用selection_sort时，全局的UNSORTED_LIST就被pop操作清空了！后面的99轮测试和30次迭代，都是对空列表执行排序——空列表的排序当然几纳秒就能完成，直接返回空数组，这就把整体平均时间拉到了离谱的57ns左右，完全不能反映真实性能。

而C++的测试就没有这个问题：

void test_selection_sort(benchmark::State &state)
{
  for (auto _ : state)
  {
    selection_sort(unsorted_arr);  // 每次调用都是值传递，自动复制原数组
  }
}

C++的selection_sort参数是std::vector<int> arr（值传递），所以每次循环都会完整复制unsorted_arr，然后对全量的10000个元素执行排序，所以基准测试的118ms是真实的排序耗时。

2. 如何修正Python的基准测试？ #

要让Python的测试反映真实性能，你需要每次调用都传入原列表的新副本，避免修改全局变量：

def test_selection_sort_benchmark(benchmark: BenchmarkFixture) -> None:
    benchmark.pedantic(
        target=selection_sort,
        args=(UNSORTED_LIST.copy(),),  # 每次测试都传新的列表副本
        rounds=100,
        warmup_rounds=5,
        iterations=30,
    )

或者用lambda包装确保每次调用都是新列表：

def test_selection_sort_benchmark(benchmark: BenchmarkFixture) -> None:
    benchmark.pedantic(
        target=lambda: selection_sort(UNSORTED_LIST.copy()),
        rounds=100,
        warmup_rounds=5,
        iterations=30,
    )

修改后，Python的基准测试时间会和C处于同一数量级（当然Python肯定还是比C慢很多，毕竟是解释型语言）。

3. 额外的实现细节对比 #

另外，你的C实现用了arr.erase(arr.begin() + smallest_idx)，vector的erase删除中间元素是O(n)时间（需要移动后续元素）；Python的list.pop(idx)也是O(n)复杂度，这部分两者逻辑一致，但C的底层执行效率更高。

总结：你看到的“Python比C++快几十万倍”完全是基准测试的bug导致的，不是真实性能差异——修正测试用例后，结果就会回归正常。

备注：内容来源于stack exchange，提问作者Gwinkamp