计数排序

[wl05]

计数排序适合整数排序，计数排序的思想就是两点：

1. 声明一个空数组counts，这个空数组的作用就是用来计数
2. 怎么计数，用待排序的数组的元素做参考作为counts的下标，对应下标的值是该元素出现的次数，这样遍历完成后就得到了排序好的顺序，然后遍历counts，得到最后的排序结果。

function countingSort(array) {
    const min = Math.min.apply(Math, array)
    const counts = []
    let sortedIndex = 0
    // 相当于把值做为下标，这样在顺序上就排好了，同时
    // 计数每个元素出现的次数，因为可能有重复的数字
    // 减去min是为了防止有负数，同时这样做可以节省空间比如排序1000-1100，只需要100个空间
    array.forEach(item => {
        counts[item - min] = (counts[item - min] || 0) + 1
    })

    counts.forEach((count, index) => {
        while (count > 0) {
            array[sortedIndex] = index + min
            sortedIndex++
            count--
        }
    })
    return array
}

let array = [-10, 1, 1, 2, 3, -10, -90]
console.log(countingSort(array))