核心思想

    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()*/

}