计数排序/Count Sort

计数排序

计数排序（Count Sort）是一种不基于比较的排序方法。

计数排序的思路是这样的，对于每一个待排序元素 a，如果知道了待排序数组中有多少个比它小的数，那么就可以直接知道在排序后的数组中 a 应该在什么位置上。比如，如果一个数组中有 3 个数是比 a 小的，那么，在排序后的数组里，a 必然会出现在第 4 位。

现在问题转化成，对于待排序数组里的一个数，如何能快速知道比它小的数字有多少个。要解决这个问题，我们不能使用比较的办法，那样时间复杂度是无法降下来，只有换一个思路，以空间换时间。因为 n 个数的取值范围是 0~n，所以，不妨使用一个大小为 n 的数组来统计从 0 到 n，每个数在待排序数组中出现的次数。这个数组类似于直方图数组，因为这种方式也被称做是基于统计的排序。直方图统计的思路简单清晰，在很多题目中都会有出现，一定要熟练掌握这种技巧。

/**
 * 计数排序
 */
export const countingSort = (arr, maxValue) => {
    let bucket = new Array(maxValue + 1);
    let sortedIndex = 0;
    let arrLen = arr.length;
    let bucketLen = maxValue + 1;

    for (let i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }

    for (let j = 0; j < bucketLen; j++) {
        while (bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }

    return arr;
}