核心思想
1: 是桶排序的特殊情况, 桶的大小为1, 省掉了桶内排序的过程
2: 不存在交换和比较过程, 是以元素本身的值决定的
适用场景
1: 数据的范围小
2: 计数排序只能给非负整数排序, 其他类型数据可尝试转化成[0,~]
3: 灵活度高, 可以实现成去重版,非稳定版,稳定版,根据自己的业务场景可自由切换
具体实现
package Sorting
import (
"Algorithms/utils"
)
//计数排序： 桶排序的特殊情况，每个桶内只有一个元素，所以省掉了桶内排序的步骤
//算法流程：1：以算法的最大值为桶的大小 2：以桶的下标为具体数值, 入桶 3：为了保证稳定性，需要额外操作
//可以用来去重
func countingSort(data []int) {
max := utils.GetMaxVal(data) +1
counts := make([]int, max)
for _,val :=range data {
counts[val]++
}
//稳定版
sum :=0
for index, num :=range counts {
sum = sum + num
counts[index] = sum
}
r := make([]int, len(data))
for i := len(data) -1; i >=0; i-- {
r[counts[data[i]] -1] = data[i]
counts[data[i]]--
}
copy(data, r)
//不去重版本
/*for index, val := range counts {
for val > 0 {
fmt.Printf("%v ",index)
val--
}
}
fmt.Println()*/
//去重输出版本
/*for index, val := range counts {
if val > 0 {
fmt.Printf("%v ",index)
}
}
fmt.Println()*/
}
