计数排序

(图片来自 计数排序 - 十大经典排序算法

思路

如果我们已知待排序序列的数值范围,其实我们可以开辟大小为该数值范围的额外空间,然后遍历一遍待排序数组,放入对应的位置,即可完成排序。该算法具有线性时间复杂度,空间复杂度则为数值范围。

分析

  • 平均、最好、最坏时间复杂度都是 $O(n + k)$,其中 $n$ 为数组长度,$k$ 为数值范围。
  • 空间复杂度也为 $O(n + k)$。
  • 算法稳定。

实现

见《🔢 排序算法 00. 代码实现》(本博客)。