排序算法（十）计数排序

  计数排序是一种是一个非基于比较的排序算法，该算法以空间换时间，通过建立额外的辅助空间，在扫描原数组将元素出现次数记录在辅助空间中，最后再计算辅助空间内的数据，可确定每个元素的位置。计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

图片演示

计数排序

算法思路步骤

1. 找出源数组中最大max、小值min；
2. 建立 max - min + 1 大小的辅助存储空间；
3. 遍历源数组，以源数组的值 - min作为辅助数组的下标，该下标对应的辅助数组的值自增壹；
4. 遍历辅助数组，辅助数组中，值大于零的下标 + min即为源数组的值，依次遍历，将值记录在结果数组中，每记录一次值时，对应的辅助数组的值增减壹，直到值为0时，跳转到下一下标，直至遍历完整个数组。

代码实现（TypeScript实现）

let originData: Array<number> = [5, 6, 7, 9, 10, 15, 13, 19, 5, 9, 13, 10];
// 求范围
let min = originData[0];
let max = min;
// 定义计数数组
originData.forEach(element => {
    if (element < min) { min = element; }
    if (element > max) { max = element; }
});
let tempData: Array<number> = new Array<number>(max - min + 1);
// 计数
originData.forEach((value) => {
    if (!tempData[value]) {
        tempData[value - min] = 1;
    } else {
        tempData[value - min]++;
    }
})
// 结果
let res: number[] = [];
let resIndex = 0;
tempData.forEach((element, index) => {
    while (element > 0) {
        res[resIndex++] = index + min;
        element--;
    }
});
console.log(res);   // [5, 5, 6, 7, 9, 10, 10, 13, 15, 19]

适用范围

1. 计数排序只适用于元素值较为集中的情况，若集合中存在最大最小元素值相差甚远的情况，则计数排序开销较大、性能较差。
2. 计数排序要求输入的数据必须是有确定范围的整数，若待排序集合中存在元素值为浮点数形式或其他形式，则需要对元素值或元素差值做变换，会加大性能消耗。