计数排序 Counting-sort

算法

计数排序,是在特定条件下,时间复杂度可为 O(n) 线性时间复杂度的排序算法。

特定条件指的是 n 个待排序数都是在 0 到 k 范围内的数。

基本思路是:

编码

go

func CountingSort(data []int, k int) {
	// 构建 0-k 的映射结构
	// 索引为数值,值为计数,表示该值的数量
	counter := make([]int, k+1)
	// 计数,统计 n 出现的次数
	for _, n := range data {
		counter[n]++
	}
    // 利用计数,计算出比n小的数的数量,进而确定n的位置
    // 确定位置用于保证排序算法的稳定性
	l := len(data)
	temp := make([]int, l)
	for i:=l-1; i>=0; i-- {
		temp[counter[data[i]]-1] = data[i]
		counter[data[i]] --
	}
	// 拷贝回data
	for i:=0; i<l; i++ {
		data[i] = temp[i]
	}
}
// 测试通过
data := []int{5, 3, 8, 1, 2, 7, 4, 0, 9, 6}
CountingSort(data, 9)
fmt.Println(data)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

若不需要考虑稳定性,则在计数统计之后,直接拷贝到原 data 即可:

// 不稳定
// 拷贝回data
func CountingSort(data []int, k int) {
	// 构建 0-k 的映射结构
	// 索引为数值,值为计数,表示该值的数量
	counter := make([]int, k+1)
	// 计数,统计 n 出现的次数
	for _, n := range data {
		counter[n]++
	}
    // 拷贝回data
    di := 0
    for i:=0; i<=k; i++ {
        for j:=1;j<=counter[i];j++ {
            data[di] = i
            di ++
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19