前面讲的都是基于比较交换的算法，那有没有不使用比较就能排序的算法呢？它们的复杂度会不会更优呢？
接下来在后面的系列文章中，我将一一介绍O(n)线性的排序方法：
- 计数排序
- 桶排序
- 基数排序
这一篇文章我们就先来学习什么是计数排序：
计数排序
计数排序是针对给定范围的队列，创建这个范围大小的数组，初始值都为0，然后遍历队列，将数字放至到对应的下标位置，如果出现1次，则计数+1，直至遍历完成，就将所有的数字都放入这个数组里了。
然后再次遍历这个数组，按照数组下标，将取出对应的值，如果计数为几，就按顺序出现几次，将这些值放入一个新数组中，遍历完成后，就可以得到有序队列了
下面，按常，举个栗子：
初始的无序数组，假设总共有12个数，假设所有值都在0-10之间取，这12个值分别为：1、3、4、6、8、9、1、2、3、10、7、5
- 创建一个长度为11的数组，初始值全设为0：[0,0,0,0,0,0,0,0,0,0,0]
- 遍历这12个值，第1个为1，将数组下标为1的位置，计数加1 ：[0,1,0,0,0,0,0,0,0,0,0]
- 第2个为3，将数组下标为3的位置，计数加1： [0,1,0,1,0,0,0,0,0,0,0,0]
... - 直到所有数字遍历完成，结果为：[0,2,1,2,1,1,1,1,1,1,1]
- 这时候，遍历这个数组，取出对应下标的值，根据次数，放到一个新队列中
- 比如，下标为0的计数为0，代表没有数字，忽略；
- 下标为1的数字计数为2，代表1出现了2次，则新队列结果为:[1,1]
- 下标为2的数字计数为1，代表2出现了1次，则往新队列中添加元素[1,1,2]
... - 最后，可以得到最终的结果[1,1,2,3,3,4,5,6,7,8,9,10]，这就是我们想要的有序队列了
计数算法的优化
如果这个序列的范围不是从0开始，而是从某个值到某个值之间，比如是500-600之间取值，这其实只用了101个空间，这时候如果从创建从0-600的初始数组，这无疑浪费了0-499的空间，计算机说不要占着茅坑不干事！
所以要优化一下，只创建101个空间大小，来放置500-600间的数，那么这个关系怎么对应上呢？
其实只要下标 + min就是我们对应的值了，比如500放到下标为0的位置，到时取出来的值时，就下标0 + 500，就是我们想到的值了
/**
* @description 实现计数算法
* @param arr: 初始的无序队列（一般为指定范围）
* @return res: 计数排序后的有序队列
*/
function countSort(arr) {
// 计算出原始数组的最大最小值
let max = arr[0]
let min = arr[0]
const len = arr.length
for(let i = 0; i< len; i++) {
if(arr[i] > max) {
max = arr[i]
}
if(arr[i] < min) {
min = arr[i]
}
}
// 计算计数数组的容量
const countLen = max - min + 1
let countArr = new Array(countLen).fill(0) // 创建计数数组，并设置所有数的计数初始值为0
// 遍历初始数组，给对应下标(arr[j] - min)计数加1
for(let j = 0; j < len; j++ ) {
countArr[arr[j] - min]++;
}
// 结果队列
let res = []
// 遍历结果队列的指针
let resIndex = 0
for(let k = 0; k < countLen; k++) {
// 如果某数计数大于0，就循环取出值
while(countArr[k] > 0) {
// 将此数放入结果队列中
res[resIndex] = k + min
// 队列指针右移
resIndex++;
// 计数减1
countArr[k]--;
}
}
return res
}
// 使用console.time()和console.timeEnd()这一句语句，会输出中间程序执行的运行时间
console.time()
const arr = [544,522,522,533,511,522,551,552,553,510,557,555]
let res = countSort(arr)
console.log('res:', res); // [ 510, 511, 522, 522, 522, 533, 544, 551, 552, 553, 555, 557 ]
console.timeEnd() // default: 4.135ms
计数算法的再次优化
之前计算排序已经实现排序的基本功能了？但是，我们会发现，它把相同的部分，使用计数方式存储后，这几个相同部分，我就分不清它在初始队列中哪个先哪个后出现的了，是一个不稳定的算法
比如:[3,1,2,1]，当计数统计后为：[2,1,1]，那么在1位置上的两个1，最终会变成:[1,1,2,3]排序后我是分不清之前是哪个1先哪个1后，如果我希望排序后，不要改变相同元素的相对位置，也就是让它变成一个稳定的算法，要怎么做呢？
要实现这个功能，其实就是把当前元素的计数改成： 前面所有元素计数之和 + 当前元素计数，这样，对应下标元素对应的那个元素的计数，就是它最终序列的位置，有一些绕，还是来讲栗子吧：
比如：
初始[3,1,2,1,5]
-
按照之前优化1的算法：
最大值max为5，最小值min为1，那么设置空间为3的计数数组[0,0,0,0,0]：- 下标0对应元素1 (下标+min，就是它所对应的元素值)，下标所在位置放置元素1的计数2, [2,0,0,0,0]
- 下标1对应元素2，下标所在位置放置元素2的计数1, [2,1,0,0,0]
- 下标2对应元素3，下标所在位置放置元素3的计数1, [2,1,1,0,0]
- 下标4对应元素5，下标所在位置放置元素5的计数1, [2,1,1,0,1]
这时，遍历计数数组，根据下标所在得出: - 下标0，对应元素是1，计数为2，所以生成新数组[1,1]
- 下标1，对应元素2，计数为1，所以生成新数组[1,1,2]
- 下标2，对应元素3，计数为1，所以生成新数组[1,1,2,3]
- 下标3，因为计数为0，忽略
- 下标5，对应元素5，计数为1，所以就生成新数组[1,1,2,3,5]
-
按照现在优化2的算法：
最大值max为5，最小值min为1，计数数组[0,0,0,0,0]：- 下标0对应元素1 (下标+min，就是它所对应的元素值)，下标所在位置放置元素1的计数2, [2,0,0]
- 下标1对应元素2，下标所在位置放置元素2的自身计数1 + 前面元素的计数2 = 计数3, [2,3,0]
- 下标2对应元素3，下标所在位置放置元素3的自身计数1 + 前面元素的计数3 = 计数4, 最终的计数数组为：[2,3,4]
- 下标3对应元素4，下标所在位置放置元素3的自身计数0 + 前面元素的计数4 = 计数4, 最终的计数数组为：[2,3,4,4]
- 下标4对应元素5，下标所在位置放置元素5的自身计数1 + 前面元素的计数4 = 计数5, 最终的计数数组为：[2,3,4,4,5]
这时候，创建一个跟原数组一样大小的空数组，从后向前遍历初始数组，根据元素获取对应计数数组中下标（元素值-min）的计数值，就是它的最终位置，并更新其计数-1，代表下一次相同元素要放置的位置：
- 遍历[3,1,2,1,5]最后一个数5,它的计数下标位置为：5-min=5-1=4,查看计数数组下标为4的值，为5，代表代表它放置在新数组的第5位[,,,,5]，此时，计数数组更新5的计数为：5-1=4，代表下一次相同元素应该放置的位置[2,3,4,4,4]；
- 遍历倒数第二个数1，它的计数下标位置：1-1=0，查看计数数组下标为0的值，为计数2，代表它放置在新数据的第2数，[,1,,,5]，此时，计数数组更新1的计数为：2-1=1，代表下一次相同元素应该放置的位置，计数数组更新为：[1,3,4,4,4]；
- 遍历倒数三个数2，它的计数下标位置: 2-1=1，查看计数数组下标为1的值，为计数3，代表它放置在新数据的第3位，[,1,2,,5]，此时，计数数组更新2的计数为：3-1=2，代表下一次相同元素应该放置的位置，计数数组更新为：[1,2,4,4,4]；
- 遍历倒数第四个数1，它的计数下标位置1-1=0，计数数组下标为1的值已经在上一次更新为1，所以此时，把它放在新数组第1的位置[1,1,2,,5],计数数组更新为[0,2,4,4,4]
- 遍历第一个数3，它的计数下标位置为：3-min = 3-1 = 2，查看计数数组下标为2的值，为4，代表它放置在新数组的第4位[1,1,2,3,5]，计数数组更新为[0,2,3,4,4]，至此，排序结束
这时候发现，越往后的出现相同元素的位置越后，这样就实现稳定的计数排序了
/**
* @description 优化版：实现稳定的计数排序
* @param arr: 初始的无序队列（一般为指定范围）
* @return res: 计数排序后的有序队列
*/
function stableCountSort(arr) {
let max = arr[0]
let min = arr[0]
const len = arr.length
for(let i = 0; i< len; i++) {
if(arr[i] > max) {
max = arr[i]
}
if(arr[i] < min) {
min = arr[i]
}
}
const countLen = max - min + 1
// 前面创建计数数组的步骤不变
let countArr = new Array(countLen).fill(0)
for(let j = 0; j < len; j++ ) {
countArr[arr[j] - min]++;
}
// 就增加了：从第2个数开始，将后面元素的计数变成与前面所有元素的计数之和
for(let z = 1; z < countLen; z++) {
// 加上前一位的计数次数（也就是之前所有元素的计数之和）
countArr[z] += countArr[z -1]
}
console.log('2222', countArr); // 此时，计数数组：[ 2, 3, 4, 4, 5 ]
// 结果队列
let res = new Array(len)
let countIndex = 0
// 对初始序列，进行从后往前遍历
for(let k = len - 1; k >= 0; k--) {
// 获取元素对应的计数
countIndex = countArr[arr[k] - min]
// 因为下标0占了一位，所以下标要减1
res[countIndex - 1] = arr[k]
console.log(res)
countArr[arr[k] - min]--;
}
return res
}
const arr1 = [3,1,2,1,5]
res = stableCountSort(arr1)
console.log('res2:', res); // [ 1, 1, 2, 3, 5 ]
计数排序的局限性
虽然计数排序的时间复杂度只有O(n)，为什么我们很少用到它呢？因为它有比较大的局限性：
- 当数列最大和最小值的差距过大时，并不适合；过大的差距意思空间上的消耗也要随之变 大。不但浪费空间，而且时间复杂度也会随之升高
- 当数列元素不是整数时，也不适合。比如小数，就无法根据元素创建对应的计数数组。
总结
- 时间复杂度：
- 获取最大最小值O(n)
- 获取计数数组O(n)
- 获取累加计数数组O(n)
- 遍历初始数组O(n)
总的是O(4n)，还是约等于O(n)
- 空间复杂度
- 创建计数数组空间O(n)
- 结果队列O(n)
总的是O(2n)，还是约等于O(n)
- 是一种典型的空间换时间的算法
- 优化后的计数排序已经是稳定的排序方法
排序算法系列文章传送门(未完，持续更新中)：
排序算法-1（javascript） 冒泡、选择、插入、希尔排序的实现
排序算法-2（javascript） 快速排序的实现
排序算法-3（javascript） 堆排序的实现
排序算法-4（javascript） 归并排序的实现
排序算法-5（javascript） 计数排序的实现
