计数排序

概要

计数排序的要点，是开辟一块连续格子组成的空间，给数据进行存储。
将数组中的数字，依次读取，存入其值对应的下标中。
储存完成后，再按照空间的顺序，依次读取每个格子的数据，输出即可。

所以，计数排序要求排序的数据，必须是有范围的整数。

效果图

解法

function countingSort(arr){
    let maxValue = Number.MIN_VALUE;
    let minValue = Number.MAX_VALUE;
    let offset = 0; // 位移，用于处理负数
    const result = [];

    // 取出数组的最大值, 最小值
    arr.forEach(num => {
        maxValue = num > maxValue ? num : maxValue;
        minValue = num > minValue ? minValue : num;
    });

    if(minValue < 0){
        offset = -minValue;
    }

    const bucket = new Array(maxValue+offset+1).fill(0); // 初始化连续的格子

    // 将数组中的每个数字，根据值放入对应的下标中，
    // `bucket[num] == n`格子的意义：存在n个数字，值为num
    arr.forEach(num => {
        bucket[num+offset]++;
    });

    // 读取格子中的数
    bucket.forEach((store, index) => {
        while(store--){
            result.push(index - offset);
        }
    });

    return result;

}