计数排序-木庄网络博客

本文摘自网络，作者，侵删。

排序简介

找出数组的最大值和最小值，创建新数组[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)
}

本文来自：简书

感谢作者：澤樹

查看原文：计数排序

相关阅读 >>

手撸Golang Go与微服务 saga模式之5

手撸Golang 结构型设计模式享元模式

Golang互斥锁 sync.mutex

Golang 快速排序与 php 快速排序

Go cassandra 示例2

win7 Go语言如何安装

Golang在linux系统上获取terminal终端的宽度

dbatool-dodba