计数排序

排序

说明

统计有限整数值域的出现次数；时间 O(n+k)，空间 O(k)。

分析

先统计每个整数值出现的次数，再按值域顺序写回结果。它不通过比较决定先后，因此在值域 k 较小时可优于比较排序。

图解推演

补充输入 [2,1,2,0]、最大值 2，计数表为 [1,1,2]，按值顺序写回得到 [0,1,2,2]。时间包含扫描 n 个输入与扫描 k 个桶两部分。这个“按次数重建整数”版本不能直接保留记录身份；要稳定排序带附加字段的记录，应使用前缀累计位置并按稳定规则分配。

查看图表代码

适用前提与边界

示例只支持 0 到 maxValue 的非负整数；值域很大时计数数组会浪费内存。

示例输入与调用

fmt.Println(CountingSort([]int{3, 1, 2, 1}, 3))

运行输出

[1 1 2 3]

完整 Go 示例

package main

import "fmt"

func CountingSort(a []int, maxValue int) []int {
	count := make([]int, maxValue+1)
	for _, x := range a {
		count[x]++
	}
	out := make([]int, 0, len(a))
	for x, n := range count {
		for ; n > 0; n-- {
			out = append(out, x)
		}
	}
	return out
}

func main() {
	fmt.Println(CountingSort([]int{3, 1, 2, 1}, 3))
}