Python中该排序机制是否为有效方案？时间复杂度是否为O(n)？

问题答复 #

1. 是否是有效的排序实现？

功能上确实可以实现升序排序，能输出符合预期的结果，但不属于实用的有效实现，存在两个明显的缺陷：

• 性能极差，远低于同复杂度级别的常规排序实现
• 存在副作用：会直接清空你传入的原始列表，因为代码中对可变对象a调用了pop原地修改方法，调用函数后外部传入的原列表会变为空，极易引发业务bug。

2. 时间复杂度是否为O(n)？

完全不是，该实现的时间复杂度为O(n²)。
你可以拆解每轮循环的操作耗时验证：
外层循环总共执行n次（n为输入列表长度），每轮循环内部执行3个线性耗时的操作：

• reduce遍历当前列表找最小值：当前列表长度为n-i，耗时O(n)
• a.index(val)遍历当前列表找最小值的下标：耗时O(n)
• a.pop(index)如果弹出的不是列表末尾元素，需要移动后续所有元素补位：耗时O(n)

三者叠加后单轮循环耗时就是O(n)，乘以外层n次循环，总时间复杂度为O(n²)，远高于你预期的O(n)。
本质上你这个是非常冗余的选择排序实现，常规选择排序单轮仅需要一次遍历就能同时找到最小值和对应下标，你的实现每轮多做了两次全量遍历，常数开销比普通选择排序还要大很多。

补充优化思路

如果要保留选择排序的思路，可以修改为如下更高效的实现，同时避免修改原数组：

def sorter(a):
    # 先拷贝原数组，避免修改外部传入的列表
    arr = a.copy()
    b = []
    while arr:
        min_val = arr[0]
        min_idx = 0
        # 一次遍历同时找最小值和下标，省掉两次冗余遍历
        for i in range(1, len(arr)):
            if arr[i] < min_val:
                min_val = arr[i]
                min_idx = i
        b.append(min_val)
        arr.pop(min_idx)
    return b

不过即使优化后，这依然是O(n²)复杂度的排序，仅适合小数据量场景使用，大数据量还是建议用Python内置的list.sort()或者sorted()方法，底层是Timsort实现，平均时间复杂度为O(nlogn)，性能远高于自定义的排序实现。

内容的提问来源于stack exchange，提问作者Lambda-Square