这是用于整数数组或以整数为键的结构的排序算法。当整数范围与输入大小相同时特别有用。
主要思想是确定整数出现的频率，并用它来确定排序顺序。
举个例子：假设我们得到数组 {1,3,1,2}.
首先确定此输入的整数范围，最大值和最小值，1 和 3。
接下来创建一个数组，称之为 counts 数组，即整数范围的大小+1，因此在本例中为 3 (3-1+1)。
迭代输入数组，增加相应条目的计数。给定输入值的计数将放置在 counts[value - min] 处。对于给定的输入，counts[0] 将保存值 1 的计数。
这会产生计数数组：{2,1,1}
现在确定累计计数，本质上是 counts[i] = counts[i-1]+counts[i]。
这会产生累积计数数组：{2,3,4}
为排序后的输入创建输出数组。
现在，以相反的顺序迭代输入。
在每一步中，检索输入数组中值的累积计数。该值将被放置在与检索到的计数 - 1 相对应的输出数组索引处。然后递减累积计数值。
在第一步中，检索值 2 且累积计数为 3。该值应放置在输出中的索引 2 (3-1) 处。
在下一次迭代中，值1，累计计数2；所以这个“1”被放置在输出的索引 1 (2-1) 处。
继续，数值3，累计次数4；将其放置在输出的索引 3 处。
最后第二次值为1，累计计数为1（因为第一次看到计数就减1了）；所以这个'1'被放置在输出的索引0处。
，了解反向迭代如何保留相等元素的顺序，从而使排序“稳定”
排序后的数组为 {1,1,2,3}
func CountingSort(in []int) []int {
// find the min/max values
min := slices.Min(in)
max := slices.Max(in)
// create the count array
counts := make([]int, max-min+1)
for _, v := range in {
counts[v-min]++
}
// determine cumulative counts
for i := 1; i < len(counts); i++ {
counts[i] = counts[i-1] + counts[i]
}
// create the output array
out := make([]int, len(in))
for i := range in {
v := in[len(in)-1-i]
out[counts[v-min]-1] = v
counts[v-min]--
}
return out
}
可以提高效率吗？请在下面留下您的意见和建议。
谢谢！
这篇文章以及本系列所有文章的代码可以在这里找到
