再谈计数排序—看了多篇文件理解记忆总结—排序算法
Author：zhoulujun Date：
计数排序概念
计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。
元素从未排序状态变为已排序状态的过程，是由额外空间的辅助和元素本身的值决定的。计数排序过程中不存在元素之间的比较和交换操作，根据元素本身的值，将每个元素出现的次数记录到辅助空间后，通过对辅助空间内数据的计算，即可确定每一个元素最终的位置。当然这是一种牺牲空间换取时间的做法，它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 [而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）。
比较性质排序算法的时间复杂度有一个理论边界，即O(N㏒₂N)，N 个元素的序列，能够形成的所有排列个数为 N!，即该序列构成的决策树叶子节点个数为 N!，由叶子节点个数可知，决策树的高度为 log_2(N!)，即由决策树根节点到叶子节点的比较次数为 log_2(N!)，由斯特灵公式，n!≈(2nπ)^½(n/3)^n，转换可得，比较性质的算法复杂度理论边界为 O(Nlog_2N) 。
计数排序特点
非比较排序
桶思想的一种
适用场景
量大但是范围小
某大型企业数万员工的年龄排序 范围（0--100）
如何快速得知高考名次（腾讯面试题） 范围（0--750）
算法过程
根据待排序集合中最大元素和最小元素的差值范围，申请额外空间
花 O(n)的时间扫描一下整个序列 A，获取最小值min和最大值max，开辟一块新的空间创建新的数组B，长度为 max - min + 1（因为申请的额外空间足以将 min 和 max 之间的所有元素记录，将待排序集合中每一个元素都记录到额外空间上）
遍历待排序集合，将每一个元素出现的次数记录到元素值对应的额外空间内；
组 B 中 index 的元素记录的值是 A 中某元素出现的次数
对额外空间内数据进行计算，得出每一个元素的正确位置；
将待排序集合每一个元素移动到计算得出的正确位置上。
算法流程解释
与比较排序注重于元素之间的比较不同，计数排序专注于找准自己的位置，而不关心自己比谁小，比谁大。其核心在于，对于任意一个属于数组array的元素number，统计其在array内出现的次数，将其以键值对的形式保存在hash，如果hash没有number，使hash[nmber] = 1,并且与max做对比是否需要重置max（max是hash的最大键，也可以理解为共有多少的桶。。），否则hash[number]++,形成hash后，将其按顺序push到新数组newArr。
计数排序实例：
先假设20个随机整数的值是：9, 3, 5, 4, 9, 1, 2, 7, 8，1，3, 6, 5, 3, 4, 0, 10, 9, 7, 9
取数组的最大值max=9，min=0，可得申请额外空间大小为：max - min +1 =10
遍历排序，记录每个元素在相应位置的出现次数，比如第一个整数是9，那么数组下标为9的元素加1，第二个整数是3，那么数组下标为3的元素加1，最终，数列遍历完毕时，数组的状态如下：
有了这个统计结果，排序就很简单了，直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次：
再看一个案列：
计数排序代码示范案列
下面是直接按照上面的步骤，js实现code
/**
* 计数排序算法
* @param arr {Array} 待排序数组
* @param min {Number|undefined} 数组中的最小值
* @param max {Number|undefined} 数组中的最小值
* @return {Array} 排序完的数组
*/
function countSort (arr, min, max) {
if (!Array.isArray(arr)) {
return arr
}
let length = arr.length
if (length < 2) {
return arr
}
// 如果不知道最大值与最小值，扫描数组，取出数组中的最大值与最小值
if (!min || !max) {
min = arr[0]
max = arr[0]
for (let i = 1; i < length; i++) {
if (min > arr[i]) {
min = arr[i]
}
if (max < arr[i]) {
max = arr[i]
}
}
}
// 开辟一块 max - min + 1的空间(数组)，
let tempArr = new Array(max - min + 1).fill(0)
// 记录每个元素在相应位置的出现次数
for (let i = 0; i < length; i++) {
if (arr[i] !== undefined) {
tempArr[arr[i]] += 1
}
}
// 将待排序集合每一个元素移动到计算得出的正确位置上
let reArr = []
for (let i = 0; i < tempArr.length; i++) {
let value = tempArr[i]
if (value !== 0) {
reArr = reArr.concat(new Array(value).fill(i))
}
}
return reArr
}这个算法，这也写，觉得好理解些，但是，比如负数，排序就无法搞。
/**
* 计数排序算法
* @param arr {Array} 待排序数组
* @return {Array} 排序完的数组
*/
function countSort2 (arr) {
let hashMap = {}
if (!Array.isArray(arr)) {
return arr
}
let length = arr.length
if (length < 2) {
return arr
}
let min = arr[0]
let max = arr[0]
for (let i = 0; i < length; i++) {
let num = arr[i]
if (hashMap[num] === undefined) {
hashMap[num] = 1
} else {
hashMap[num]++
}
if (i === 0) {
continue
}
if (num > max) {
max = num
}
if (num < min) {
min = num
}
}
let reArr = []
for (let hashIndex = min; hashIndex < max + 1; hashIndex++) {
let repeatTimes = hashMap[hashIndex]
if (repeatTimes !== undefined) {
reArr = reArr.concat(new Array(repeatTimes).fill(hashIndex))
}
}
return reArr
}计数排序测试
let testArr = [10, 7, 1, 0, 100, 4, 5, 2, 70] console.log(countSort(Object.assign([], testArr))) console.log(countSort2(Object.assign([], testArr)))
参考文章：
排序算法（八）：计数排序 https://www.jianshu.com/p/86c2375246d7
什么是计数排序？ https://www.cnblogs.com/kyoner/p/10604781.html
五分钟学会一个有意思的排序：计数排序 https://www.v2ex.com/t/511806
排序算法入门(三) 计数排序，桶排序 https://zhuanlan.zhihu.com/p/46877267
https://baike.baidu.com/item/计数排序/8518144?fr=aladdin
转载本站文章《再谈计数排序—看了多篇文件理解记忆总结—排序算法》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/SortingAlgorithms/8263.html