一、定义
计数排序几乎是唯一一个不基于比较的排序算法，作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
二、算法思想
将输入的数据值转化为键存储在额外开辟的数组空间中。
三、具体实现
function countSort(arr) {var index = 0;var len = arr.length;var maxValue = Math.max.apply(null, arr); // 最大值var result = new Array(maxValue+1); // 结果数组// 把各个数组中对应的元素计数加一for(var i = 0; i < len; i++) {if(!result[arr[i]]) {result[arr[i]] = 0;}result[arr[i]]++;}// 按照计数的元素进行排序for(var j = 0; j < maxValue + 1; j++) {while(result[j] > 0) {arr[index++] = j;result[j]--;}}return arr; } console.log(countSort([53,115,9,72,11,6,3,19]));
四、效率分析
计数排序不改变相同元素之间原本相对的顺序，因此它是稳定的排序算法。
1、时间复杂度
最坏的情况：时间复杂度为O(n+k)；
最佳的情况：时间复杂度为O(n+k)；
平均来讲，时间复杂度为O(n+k)。
n表示数据规模，k表示桶的个数。
2、空间复杂度
空间复杂度为常量O(k)。
