计数排序

计数排序（Counting sort）是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组 C ，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。

计数排序的基本思想是：对每一个输入元素 x，确定小于 x 的元素个数。利用这一信息就可以直接把 x 放到它在数组中的位置上了。例如，如果有 17 个元素小于 x，则 x 就应该在第 18 个输出位置上。当有几个元素相同时，这一方案要略做修改，因为不能把它们放在同一个输出位置上。

代码如下（Go 语言版）

func countingSort(arr []int) []int {
    if len(arr) < 2 {
        return arr
    }
    // 寻找最大的元素
    max := arr[0]
    for i := 0; i < len(arr); i++ {
        if arr[i] > max {
            max = arr[i]
        }
    }

    // 初始化一个长度为 max+1 的数组
    countList := make([]int, max+1, max+1)

    // 计数
    for i := 0; i < len(arr); i++ {
        countList[arr[i]]++
    }

    // 统计计数累计值
    for i := 1; i < max+1; i++ {
        countList[i] += countList[i-1]
    }

    //初始化返回数组
    outPutList := make([]int, len(arr))
    // 将元素放到正确的位置上
    for i := 0; i < len(outPutList); i++ {
        outPutList[countList[arr[i]]-1] = arr[i]
        countList[arr[i]]--
    }
    return outPutList
}

可以看出，计数排序的过程中一共经历了四次遍历，总的时间代价为 O(2k+2n)，其中，k 为数组元素中的最大值，n 为数组的长度。在实际工作中，当 k=O(n) 时，采用计数排序，运行的时间为 O(n)。需要注意的是，计数排序只适用于范围较小的非负整数序列。

计数排序的一个重要性质就是它是稳定的：具有相同值的元素在输出数组中的相对次序与它们在输入数组的相对次序相同。也就是说，对两个相同的数来说，在输入数组中先出现数，在输出数组中也位于前面。通常，这种稳定性只有当进行排序的数据还附带卫星数据时才比较重要。计数排序的稳定性很重要的另一个原因是：计数排序经常会被用作基数排序算法的一个子过程。