小撒是一只好学的小鸭子，这天，小撒在学习算法
比较排序与线性时间排序
此前我们介绍的排序方法都是基于比较的，而基于比较的排序方法存在Ω(n * log(n))的理论下界。
接下来我们要介绍的，是一系列能在线性时间内完成排序的算法。
不过需要注意的是，相较于基于比较的算法，这些线性时间排序算法，并不具有普适性。
计数排序（Counting Sort）
计数排序便是一种线性时间排序算法。这里我们需要先假设：参与排序的所有元素，都是介于 0 至 某个有限整数 k 之间的整数。
我们首先创建一个长度为k+1的计数数组，k为数组中的最大元素。计数数组中的每一位用来对原数组中相应元素出现的个数计数：
假设原数组是[2,3,1,2,0,3]，其中最大元素值为3，因此计数数组共有3 + 1 = 4个槽，分别记录原数组中0~3的元素个数，例如这里的[1,1,2,2]代表原数组有1个0，1个1，2个2以及2个3。
在此时，如果我们从头遍历计数数组，依次输出按照个数输出元素，即1个0，1个1，2个2以及2个3，那么我们就能得到排序后的结果：[1,1,2,2,3,3]。
不过呢，我们想要的不仅如此，接下来，我们需要进一步处理。
稳定排序
在这里，我们需要的实现一个稳定排序。假设我们排序的是这样的数组：[ { id: 21, value: 3 }, { id: 15, value: 3 }... ]，基于元素的value属性对数组排序，那么仅仅是以上的操作就不能满足要求了：因为在计数数组中我们只能对value计数，却无法保留元素的整体信息。同时我们想要的是一个稳定排序算法，这意味着，若在原数组中元素a和b有相同的value，且a出现在b的左侧，那么在排序之后，我们仍希望a出现在b的左侧。
于是我们首先对计数数组进行一番操作：
这里我们将计数数组每一位的值，变为左侧（包括自身所有计数的累加），例如第0位为1，第1位为1 + 1 = 2，第2位为1 + 1 + 2 = 4等。转换之后第k位（最后一位）的值应当为原数组的长度。
如图所示，我们从数组右侧开始扫描数组，逐一处理：这里为了便于描述，我们先关注于每当遇到元素2时该如何处理。
首先我们来思考，计数数组中2所对应的值4代表了什么。这里代表了原数组中不大于2的元素共有4个，那么当我们从右侧开始扫描这个数组时候，遇到的第一个元素2，就应当出现在排序数组下标为4 - 1 = 3的位置上。当我们继续扫描遇到下一个元素2的时候，自然应该把它放到第一个2的左侧。
因此，我们从右侧开始扫描原数组，对每一个元素都通过计数数组获得它应该被放置到的位置，同时将计数数组中相应的值-1。直到原数组扫描完成，我们也就取得了排序后的数组。
代码示例（js）
const sort = (arr) => {
const max = getMax(arr)
const counters = Array(max).fill(0)
arr.forEach((item) => {
counters[item - 1]++
})
counters.forEach((item, index) => {
if (index !== 0) {
counters[index] += counters[index - 1]
}
})
const rtn = Array(arr.length)
for (let i = arr.length - 1; i >= 0; i--) {
const item = arr[i]
const pos = counters[item - 1] - 1
rtn[pos] = item
counters[item - 1] = pos
}
return rtn
}
小结
计数排序是一种线性时间排序，即Θ(n)。当然这里也有个问题：如果数组中的最大元素较大，我们需要创造一个巨大的计数数组，空间成本太高。对于这一问题，接下来我们将介绍基数排序。
