首页 > 其他分享 >数组排序简介-计数排序(Counting Sort)

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

时间:2024-10-31 20:19:26浏览次数:8  
标签:Sort arr Counting nums 计数 num 数组 排序

基本思想

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

算法步骤

  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]为例,演示一下计数排序算法的整个步骤。

适用场景

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

排序稳定性

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

代码实现

func countingSort(arr []int) []int {
    if len(arr) == 0 {
        return arr
    }

    // 找到最大值和最小值
    minVal, maxVal := arr[0], arr[0]
    for _, v := range arr {
        if v < minVal {
            minVal = v
        }
        if v > maxVal {
            maxVal = v
        }
    }

    // 计数数组
    count := make([]int, maxVal-minVal+1)
    for _, v := range arr {
        count[v-minVal]++
    }

    // 构建排序后的数组
    result := make([]int, len(arr))
    index := 0
    for i, c := range count {
        for j := 0; j < c; j++ {
            result[index] = i + minVal
            index++
        }
    }

    return result
}


func main() {
    arr := []int{4, 2, 2, 8, 3, 3, 1}
    sortedArr := countingSort(arr)
    fmt.Println(sortedArr)
}

标签:Sort,arr,Counting,nums,计数,num,数组,排序
From: https://blog.csdn.net/Runing_WoNiu/article/details/143355189

相关文章

  • 数组排序简介-快速排序(Quick Sort)
    基本思想        采用经典的分治策略,选择数组中某个元素作为基准数,通过一趟排序将数组分为独立的两个子数组,一个子数组中所有元素值都比基准数小,另一个子数组中所有元素值都比基准数大。然后再按照同样的方式递归的对两个子数组分别进行快速排序,以达到整个数组有序。......
  • order by 、sort by、distribute by、group by、cluster by的区别
    1.orderby:用途:主要用于对查询结果进行排序。返回的结果集是全局有序的。SELECT*FROMemployeesORDERBYsalaryDESC;2.SORTBY用途:主要用于对分布式查询结果进行排序。每个节点(分区)分别进行排序,但返回的结果集不一定全局有序。适用于Hive等大数据处理系统。SELEC......
  • 拓扑排序
    拓扑序1、在做DAGDP时,按拓扑序转移,状态可转移完全2、从拓扑序小的点连向拓扑序大的点,一定不会成环3、统计结点\(x\)可以到达的点数(待解决)DirectingEdges根据性质2,对有向边构成的图跑拓扑,拓扑序小的连向大的即可正确性由性质2易知,待证明P3953[NOIP2017提高组]逛公园本......
  • Day26--冒泡排序
    Day26--冒泡排序冒泡排序无疑是最为出名的排序算法之一:总共有八大排序!冒泡的代码还是相当简单的,两层循环:外层冒泡轮数,里层依次比较:江湖中人人尽皆知。我们看到嵌套循环:应该立马就可以得出这个算法的时间复杂度为O(n²)。思考:如何优化?1.冒泡排序的思路理解:一、冒泡排序的起......
  • qsort排序
    在体操比赛中,每位选手的得分是由多名裁判综合打分所得。现在已经汇总了N名选手的个人总得分(选手的编号依次为1,2,……N),请你设计程序找出第K名选手在所有选手中的排名。输入说明:第一行是N和K,N表示运动员的个数,K是选手序号;第二行依次是这N位运动员的个人总得分。输出说明:第K名(从1开......
  • xtu oj 逆序数(小数据) //冒泡排序
    题目描述给你一个序列x1,x2,…,xn,如果数对<xi,xj>,其中i<j,而xi>xj我们称之为逆序数对。一个序列的逆序数对的数目,称为这个序列的逆序数。比如说序列312,逆序数对为<3,1>和<3,2>,所以这个序列的逆序数为2。现在给你一个数字序列,请求其逆序数。输入每个样例为两行......
  • 项目进度计划中的任务如何优先排序
    项目进度计划中的任务优先排序取决于多个因素:任务的紧迫性、依赖关系、资源可用性、项目关键路径以及潜在风险。通常,在确定任务优先级时,应首先考虑关键路径上的任务,因为这些任务直接影响项目完成的总时长。接着,考虑那些有着严格截止日期或是对项目成败至关重要的任务。资源的分配......
  • 【数据结构多彩画卷】不要只会普通的二叉树了 , 你听说过用二叉树来排序吗? 【二叉搜索
    本篇会加入个人的所谓鱼式疯言❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言而是理解过并总结出来通俗易懂的大白话,小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.......
  • 【信奥赛·算法基础】插入排序:算法解析与C++实现
    序言插入排序(InsertionSort)是一种简单的排序算法,就像是我们在打扑克牌时,整理手中牌的过程。一、基本原理插入排序的基本思想是:将待排序的元素插入到已经有序的部分序列中合适的位置,直到所有元素都插入完毕,整个序列就变为有序序列。二、算法步骤从第二个元素开始(假设第......
  • 排序算法在最坏情况下的性能差异:深入分析
    目录1.排序算法简介2.最坏情况示例分析2.1插入排序2.2归并排序2.3快速排序2.4堆排序3.性能差异与优化策略4.拓展知识:算法选择与优化5.结语        在软件工程中,排序算法是数据处理的基石。不同的排序算法在不同情况下表现出不同的性能。本文将通过......