计数排序
站在巨人的肩膀上能够事半功倍！参考 程序员小灰大佬 写的文章 漫画： 计数排序
官方解释：计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 [1] 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序，堆排序）
思想：
-
为原来的数组分配额外的空间(数组)， 用来存储原数组中出现的次数
找出原数组的最大值，最小值，计算所需额外的空间大小
空间大小为 原数组的 最大值 - 最小值
定义 这个额外的空间，用 0 填满
计算 数组中 每个 数 出现的次数 并且
遍历 定义的数组，输出
example：
9，3，5，4，9，1，2，7，8，1，3，6，5，3，4，0，10，9 ，7，9
该数组中数值范围在 0 - 10 所以 分配空间大小为: 10 - 0 + 1 = 11。
用 0 填满该数组， 如图：
[图片上传失败...(image-beeb90-1573208594202)]
比如第一个数：9，即 数组下标 为 9 的元素加1，即 0 + 1 = 1， 如图：
解决下标问题： 下标就是 原数组的值 - 最小值： 9 - 0
img
第二个整数是3，那么数组下标为3的元素加1：
img
以此类推，最终结果如图：
[图片上传失败...(image-e8070c-1573208594202)]
然后遍历数组存入一个空数组中即可。
代码（JavaScript）：
/**
*
* @param {*Array} nums
*/
function countSort(nums) {
// 找出数组中数值的范围 example： [-1,3,2,0]。 范围为： 3 - (-1) + 1 = 5 个 [-1, 0, 1, 2, 3]
let max = nums[0], // 假设 第一个数最大
min = nums[0], // 假设 第一个数最小
res = [];
for (let i = 1; i < nums.length; i++) {
// 找出数组中的最大值
max = nums[i] > max ? nums[i] : max;
// 找出数组中最小值
min = nums[i] > min ? min : nums[i];
}
// 求出 数组 额外的空间大小
const len = max - min + 1;
// 定义一个 额外的 数组 大小为 数组的个数 即 len， 并设为 0
const arr = Array(len).fill(0);
// 计算 数组中 每个数 出现的次数，并且对应好位置
for (let num of nums) {
arr[num - min]++;
}
// 遍历 我们定义的数组，存入到 res 中
for (let i = 0; i < len; i++) {
while (arr[i]) {
res.push(min + i); // 数组下标 加上 最小值 就是原数组中的值（排序好了）
arr[i]--;
}
}
return res
}
console.log(countSort([9, 3, 5, 4, 9, 1, 2, 7, 8, 1, 3, 6, 5, 3, 4, 0, 10, 9, 7, 9]));
// [ 0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10 ]
每一点知识转化为自己的，自己才能变得更加强大！
