计数排序

计数排序

计数排序(Counting sort) 是一种稳定的线性时间排序算法.计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C 来将A中的元素排到正确的位置。

算法原理

计数排序的算法原理：

• 找出待排序的数组中最大和最小的元素.
• 统计数组中每个值为i的元素出现的次数，存入数组C的第i项.
• 对所有的计数累加(从C中的第一个元素开始，每一项和前一项相加).
• 反向填充目标数组：将每个元素 i放在新数组的第C[i]项，每放一个元素就将C[i]减去1.

计数排序算法实现:

package main

import "fmt"

// 计数排序
func CountingSort(data []int)  {
    if len(data) <= 1 {
        return
    }

    min, max := CountMaxMin(data)

    temp := make([]int, max+1)

    for i := 0; i < len(data); i++ {
        temp[data[i]]++
    }

    var index int
    for i := min; i < len(temp); i++ {
        for j := temp[i]; j > 0 ; j-- {
            data[index] = i
            index++
        }
    }
}

func CountMaxMin(data []int) (int, int) {
    min, max := data[0], data[0]
    for i := 1; i < len(data); i++ {
        if min > data[i] {
            min = data[i]
        }

        if max < data[i] {
            max = data[i]
        }
    }
    return min, max
}

func main()  {
    arr := []int{33,11,55,7,44,1}
    CountingSort(arr)
    fmt.Println(arr)
}

运行结果:

countingSort: [1 7 11 33 44 55]

计数排序在特定的情况下，排序效率极高，但是如果排序的计数空间范围过大，而实际元素个数非常小的情况，效率就会非常差，比如，我只有3个元素，3，1，500000，这样的情况其实是不适合用计数排序的，这一点需要注意。

复杂度

• 最佳情况：$T(n) = O(n+k)$
• 最坏情况：$T(n) = O(n+k)$
• 平均情况：$T(n) = O(n+k)$
• 空间复杂度：$O(k)$
• 稳定性：稳定
• 排序方式：Out-place