计数排序

计数排序(Counting Sort)是一种O(n)的排序算法，其思路是开一个长度为maxValue-minValue+1的数组，然后
分配。扫描一遍原始数组，以当前值-minValue作为下标，将该下标的计数器增1。
收集。扫描一遍计数器数组，按顺序把值收集起来。
举个例子，nums=[2, 1, 3, 1, 5], 首先扫描一遍获取最小值和最大值，maxValue=5, minValue=1，于是开一个长度为5的计数器数组counter，
分配。统计每个元素出现的频率，得到counter=[2, 1, 1, 0, 1]，例如counter[0]表示值0+minValue=1出现了2次。
收集。counter[0]=2表示1出现了两次，那就向原始数组写入两个1，counter[1]=1表示2出现了1次，那就向原始数组写入一个2，依次类推，最终原始数组变为[1,1,2,3,5]，排序好了。
计数排序本质上是一种特殊的桶排序，当桶的个数最大的时候，就是计数排序。

extension Array where Element == Int {
    mutating func counterSort() -> Array{
        guard let max = self.max(),
              let min = self.min()
        else { return []}

        let range = max - min + 1
        var counter = Array<Element>(repeating: 0, count: range)
        
        for item in self {
            let index = item - min
            counter[index] += 1
        }
        var newArr = Array<Element>()
        for (index, item) in counter.enumerated() {
            var i = item
            while i > 0 {
                newArr.append(index + min)
                i -= 1
            }
        }
        return newArr
    }
}

引用

计数排序