js 实现计数排序

// 计数排序
// 稳定性：稳定
// 定义一个数组，将数组中每个元素出现的次数以数组形式保存起来，数组索引值即为具体 key，数组索引对应的元素值即为该索引值出现的次数
// 再将保存起来的次数的数字依次放入原数组
function countingSort(arr, maxValue) {
    let bucket = new Array(maxValue + 1);
    let sortedIndex = 0; // 代表传入数组的索引
    let arrLength = arr.length;
    let bucketLength = maxValue + 1;
    for (let i = 0; i < arrLength; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }
    for (let j = 0; j < bucketLength; j++) {
        // 只要当前索引下次数不为 0 ，则继续遍历
        while (bucket[j] > 0) {
            // 将原数组对应位置放入当前值，当前值即 j，同时将 sortedIndex++
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }
    return arr;
}
console.log("计数排序");
console.log(countingSort([6, 3, 7, 8, 2, 4, 0, 1, 6, 5], 15));