给定带优先级的无限大数组，如何实现O(n)时间复杂度的升序排序？

哈哈，这个面试题我当初也踩过坑！一开始满脑子都是快排、归并这些常规排序，死活想不到怎么突破O(nlogn)的下界，后来才明白，这题的核心在于线性时间排序的前提条件——常规比较排序的O(nlogn)是理论下界，但非比较类排序可以在特定条件下做到O(n)。

能实现O(n)排序的几种方案 #

这些方法都依赖于优先级的特定属性，面试时如果没明确说明，其实可以主动追问面试官优先级的取值范围、分布特性：

• 计数排序：如果优先级是有限范围内的整数（比如0到100，或者其他固定区间），这方法最适用。步骤很简单：
  1. 先遍历一遍数组，统计每个优先级出现的次数
  2. 计算前缀和，确定每个优先级在结果数组中的起始位置
  3. 再遍历原数组，把每个元素放到对应位置就行
     时间复杂度是O(n + k)，当k（优先级的取值范围大小）远小于n或者是常数时，就等价于O(n)。
• 桶排序：如果优先级的分布比较均匀（比如在[0,1000]区间内均匀分布），可以把整个区间拆成若干个桶，每个桶里的元素数量会很少，甚至可以直接用插入排序处理。当桶的数量足够多，每个桶内元素数趋近于常数时，整体时间就是O(n)。
• 基数排序：要是优先级是可以拆分成多个独立部分的数值（比如十进制数的每一位），可以按位依次排序，每一位用计数排序来实现。整体时间是O(d*(n + k))，d是位数，k是每一位的取值范围，当d是常数时，就是O(n)。

关于你当时用常规排序的合理性 #

其实完全不用懊恼！题目只说了“无限大数组”和“优先级”，没给出优先级的任何额外信息——如果没有这些前提，线性时间排序根本不可能实现（毕竟比较排序的O(nlogn)下界是经过严格证明的）。你当时选择常规排序，是在信息不足情况下的合理应对。

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