学习动机

计数排序从不比较两个元素。它直接将元素的值用作count数组的索引，因此能够在线性时间内运行。

为什么要学习计数排序？

• 线性时间：它的运行时间为 O(n + k)，其中 n 是元素数量，k 是值的范围。当 k 较小时，它比 O(n log n) 更快。
• 稳定（仔细实现时）：它是基数排序的基础，基数排序会连续执行多轮计数排序。
• 不同的思路：通过统计值来排序，而不是比较值。

代价是：计数数组需要 O(k) 的内存，因此当值的范围很大时并不适用（例如，对少量最大值达 10 亿的数字排序）。