• 数组排序简介-计数排序(Counting Sort)


    基本思想

            通过统计数组中每个元素在数组中出现的次数,根据这些统计信息将数组元素有序的放置到正确位置,从而达到排序的目的。

    算法步骤

    1. 计算排序范围遍历数组,找出待排序序列中最大值元素 nums_max和最小值元素 nums_min,计算出排序范围为 nums_max−nums_min+1。

    2. 定义计数数组:定义一个大小为排序范围的计数数组 countscounts,用于统计每个元素的出现次数。其中:
             数组的索引值 num−nums_min 表示元素的值为 num。
             数组的值 counts[num−nums_min] 表示元素 num 的出现次数。

    3. 对数组元素进行计数统计:遍历待排序数组 nums,对每个元素在计数数组中进行计数,即将待排序数组中「每个元素值减去最小值」作为索引,将「对计数数组中的值」加 1,即令 counts[num−nums_min] 加 1。

    4. 生成累积计数数组:从 counts 中的第 1 个元素开始,每一项累家前一项和。此时 counts[num−nums_min] 表示值为 num 的元素在排序数组中最后一次出现的位置。

    5. 逆序填充目标数组:逆序遍历数组 nums,将每个元素 num 填入正确位置。

    6. 将其填充到结果数组 res 的索引 counts[num−nums_min]处。

    7. 放入后,令累积计数数组中对应索引减 1,从而得到下个元素 num 的放置位置。

        以 [3,0,4,2,5,1,3,1,4,5]为例,演示一下计数排序算法的整个步骤。

    适用场景

            计数排序一般用于整数排序,不适用于按字母顺序、人名顺序排序

    排序稳定性

            由于向结果数组中填充元素时使用的是逆序遍历,可以避免改变相等元素之间的相对顺序。因此,计数排序是一种 稳定排序算法

    代码实现

    1. func countingSort(arr []int) []int {
    2. if len(arr) == 0 {
    3. return arr
    4. }
    5. // 找到最大值和最小值
    6. minVal, maxVal := arr[0], arr[0]
    7. for _, v := range arr {
    8. if v < minVal {
    9. minVal = v
    10. }
    11. if v > maxVal {
    12. maxVal = v
    13. }
    14. }
    15. // 计数数组
    16. count := make([]int, maxVal-minVal+1)
    17. for _, v := range arr {
    18. count[v-minVal]++
    19. }
    20. // 构建排序后的数组
    21. result := make([]int, len(arr))
    22. index := 0
    23. for i, c := range count {
    24. for j := 0; j < c; j++ {
    25. result[index] = i + minVal
    26. index++
    27. }
    28. }
    29. return result
    30. }
    31. func main() {
    32. arr := []int{4, 2, 2, 8, 3, 3, 1}
    33. sortedArr := countingSort(arr)
    34. fmt.Println(sortedArr)
    35. }

  • 相关阅读:
    05-树8 File Transfer
    华为机试 - 高效的任务规划
    ERROR LINK2019 无法解析的外部符号的常见错因
    常见的文件系统格式
    不同朝向的房间,怎么选择舒适的墙布颜色?-江南爱窗帘十大品牌
    Tangle:不同于区块链的分布式账本
    07-流媒体-RTMP推流
    详细讲解FuzzBench如何添加新的Fuzzer
    [格式化字符串漏洞+堆溢出] Suctf2019_sudrv
    使用Jan,把你的PC变成AI机器!支持在Windows,MacOS,Linux上运行大语言模型
  • 原文地址:https://blog.csdn.net/Runing_WoNiu/article/details/143355189