已知元素来自有限集合时，列表排序的时间复杂度是多少？

当待排序元素属于有限取值集合时，完全可以突破比较排序O(nlogn)的平均时间复杂度下界，实现线性时间O(n)（或近似线性）的排序效率——这类算法不依赖元素间的两两比较，而是利用元素取值范围有限的特性直接映射位置。

核心原理 #

比较排序的O(nlogn)下界基于决策树模型：每一次比较对应决策树的一个分支，要确定n个元素的顺序，决策树至少需要n!个叶子节点，树高为Ω(logn!)=Ω(nlogn)。而线性排序算法（如计数排序、基数排序）跳过了两两比较，通过统计元素出现频次或按位映射的方式直接构建有序数组，因此不受这个下界限制。

具体场景示例 #

1. 仅含0和1的列表 #

你提到的方法正是计数排序的简化版，确实能实现O(n)时间复杂度：

• 遍历一次数组，统计0和1的出现次数（O(n)）
• 直接构造由对应数量的0和1组成的新数组（O(n)）

用Python实现的示例代码：

def sort_binary_list(arr):
    zero_count = arr.count(0)
    return [0] * zero_count + [1] * (len(arr) - zero_count)

2. 元素为0到100的整数 #

同样用计数排序，时间复杂度为O(n + k)，其中k是取值范围的大小（这里k=101，是常数），因此整体等价于O(n)：

• 初始化长度为101的计数数组，初始值全为0
• 遍历原数组，对每个元素x，将计数数组的第x位加1
• 遍历计数数组，按顺序将元素x重复计数数组[x]次，放入结果数组

3. 仅含英文字符的字符串 #

分两种情况处理：

• 单个英文字符：如果是小写/大写字母（各26种取值），直接用计数排序，统计每个字母的出现次数后重构有序数组，时间O(n)
• 英文字符串（长度固定）：用基数排序，从最低位到最高位依次对每个字符进行计数排序，时间复杂度为O(n * d)，其中d是字符串的固定长度（d为常数时，整体是O(n)）

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