该排序算法的时间复杂度能否进一步优化？（适配10万+元素场景）

原实现代码 #

import random
import timeit

start = timeit.default_timer()

array = list(range(1, 11))
random.shuffle(array) 

new_array = []

minimal_num = 0

while len(new_array) < len(array):
    for i in range(len(array)):
        if array[i] - minimal_num == 1:
            minimal_num = array[i]
            new_array.append(minimal_num)

stop = timeit.default_timer()
print('Time: ', stop - start)  

问题描述 #

实际场景中需要处理10万+元素的列表，尝试过纯函数实现但性能相近，询问该排序算法的时间复杂度能否进一步优化？

原算法分析 #

你的算法时间复杂度是O(n²)：外层循环最多执行n次（n为数组长度），每次外层循环都要完整遍历一次数组（n步操作）。处理10万级数据时，O(n²)的复杂度会带来百万级甚至亿级的操作量，性能必然低下。

优化方案 #

从你的算法逻辑推测，数组元素大概率是连续正整数（比如从1到N的无重复整数），针对不同场景有两种高效优化方向：

1. 连续正整数场景的最优方案

如果数组是从start到end的连续无重复整数（比如示例中的1到10），完全不需要遍历排序，直接生成有序数组即可，时间复杂度为O(n)（甚至可视为O(1)，无需处理原数组）：

# 假设原数组是1到len(array)的连续整数
new_array = list(range(1, len(array)+1))

这种方式跳过了所有排序计算，直接利用元素连续性生成结果，是该场景下的极致优化。

2. 范围有限整数的通用优化（计数排序）

如果元素是范围有限的整数（比如取值在[min_val, max_val]之间，且max_val - min_val远小于n），可以用计数排序，时间复杂度为O(n + k)（k是取值范围的大小）：

def counting_sort(arr):
    if not arr:
        return []
    min_val = min(arr)
    max_val = max(arr)
    # 创建计数数组统计每个数值的出现次数
    count = [0] * (max_val - min_val + 1)
    for num in arr:
        count[num - min_val] += 1
    # 遍历计数数组生成有序结果
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([min_val + i] * count[i])
    return sorted_arr

# 测试10万级数据
array = list(range(1, 100001))
random.shuffle(array)
start = timeit.default_timer()
new_array = counting_sort(array)
stop = timeit.default_timer()
print('Time: ', stop - start)

计数排序通过统计数值出现次数直接生成有序数组，彻底避免了O(n²)的嵌套遍历，处理10万级数据的性能会比原算法提升几个数量级。

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