计数排序

排序简介

找出数组的最大值和最小值，创建新数组[max+1]， 原数组值等于新数组下标时， 新数组值加一，最后把新数组下标按值的个数输出即排序完成

图解参考https://www.cnblogs.com/kyoner/p/10604781.html

复杂度

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

golang实现

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)
}