您现在的位置是:首页 > 正文

计数排序(counting sort)

2024-02-01 00:54:14阅读 2

计数排序(Counting sort)是一种稳定的线性时间排序算法。计数排序使用一个额外的数组 C ,其中第i个元素是待排序数组A中值等于 i的元素的个数。然后根据数组 C 来将 A中的元素排到正确的位置。

计数排序特征

当输入的元素是n个 0 到k 之间的整数时,它的运行时间是 Θ \Theta Θ (n+k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。

由于用来计数的数组 C 的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。例如:计数排序是用来排序0到100之间的数字的最好的算法,但是它不适合按字母顺序排序人名。但是,计数排序可以用在基数排序算法中,能够更有效的排序数据范围很大的数组。

通俗地理解,例如有10个年龄不同的人,统计出有8个人的年龄比A小,那A的年龄就排在第9位,用这个方法可以得到其他每个人的位置,也就排好了序。当然,年龄有重复时需要特殊处理(保证稳定性),这就是为什么最后要反向填充目标数组,以及将每个数字的统计减去1。算法的步骤如下:

  1. 找出待排序的数组中最大和最小的元素
  2. 统计数组中每个值为 i的元素出现的次数,存入数组 C 的第i项
  3. 对所有的计数累加(从C 中的第一个元素开始,每一项和前一项相加)
  4. 反向填充目标数组:将每个元素 i放在新数组的第 C[i]项,每放一个元素就将 C[i]}减去1

#算法实现

#include <iostream>

using namespace std;

int main()
{
    int num = 0;
    
    cout << "how many nums you want sort?" << endl;
    cin >> num;
    if (num <= 0)
    {
        return 0;
    }
    
    int i = 0;
    int a[num]={};//array wait to sort
    int a_sorted[num]={0};//array sorted
    cout << "enter number to sort one by one, end with enter" << endl;
    
    //get array to sort
    while (i<num)
    {
        cin >> a[i];
        i++;
    }
    
    //get min and max in array
    int min = a[0];
    int max = a[0];
    for (int i= 1;i < num;i++)
    {
        if (min > a[i])
        {
            min = a[i];
        }
        if (max < a[i])
        {
            max = a[i];
        }
    }
    
    //count number of a[i] appear and save to c[]
    int c_num = max-min+1;
    int c[c_num] = {0};
    for(int i = 0;i < num;i++)
    {
        c[a[i]-min]++;
    }
    
    //accumulate c[i]
    for(int i = 1;i < c_num;i++)
    {
        c[i] += c[i-1];
    }
    
    //fill sorted array reversely
    for(int i = num;i > 0;i--)
    {
        a_sorted[c[a[i-1]-min]-1] += a[i-1];
        --c[a[i-1]-min];
    }
    //output
    
    for(int i = 0;i < num;i++)
    {
        cout<<a_sorted[i]<< ", ";
    }
    return 0;
}

Reference
[1].https://zh.wikipedia.org/wiki/计数排序
[2].https://www.geeksforgeeks.org/counting-sort/

网站文章

  • JAVA中四种线程池

    JAVA中四种线程池

    四种线程池newFixedThreadPoolnewCachedThreadPoolnewSingleThreadExecutornewScheduledThreadPool newFixedThre...

    2024-02-01 00:53:40
  • 轻量级日志管理系统-loki 简单部署

    轻量级日志管理系统-loki 简单部署

    使用grafana开发的loki工具,10分钟手动搭建一个轻量级日志管理系统

    2024-02-01 00:53:32
  • 测试开发工程师面试总结(二)——算法篇

    算法也属于常见面试内容之一,但基本不会超过《剑指offer》的范围,在此附上一篇简书上整理的内容: 第二版java解法 常见的面试题包括以下几类:字符串操作,文件输入输出流及统计,矩阵操作,单例模式等。 1.针对字符串的操作:如字符串反转、字符串去重、含有左右括号的字符串匹配。 含有左右括号的字符串匹配的题目及代码如下: 给定一个字符串,其中的字符只包含三种括号:花...

    2024-02-01 00:53:04
  • 适合 Go 新手学习的开源项目——在 GitHub 学编程

    适合 Go 新手学习的开源项目——在 GitHub 学编程

    作者:HelloGitHub-小鱼干&amp;卤蛋 故事要从 2007 年说起。因为受够了 C++ 煎熬的 Google 首席软件工程师 Rob Pike 召集 Robert Griesemer 和 ...

    2024-02-01 00:52:57
  • 怎么制作gif动态图 QQ动态表情包怎么制作

    怎么制作gif动态图 QQ动态表情包怎么制作

    在平时的聊天中经常会使用到GIF动图,不仅仅可以缓解气氛,还很有趣,那这些动态图是如何制作的呢?没有想象的那么难,今天来看看怎么制作的吧! 1、先准备好素材,要制作什么样的动图,可以是图片也可以是...

    2024-02-01 00:52:50
  • 系统架构设计专业技能 · 系统工程与系统性能

    系统架构设计专业技能 · 系统工程与系统性能

    系统工程的生命周期阶段包括。

    2024-02-01 00:52:42
  • java 接口bean_详解Spring中接口的bean是如何注入的

    java 接口bean_详解Spring中接口的bean是如何注入的

    java 接口bean_详解Spring中接口的bean是如何注入的

    2024-02-01 00:52:14
  • Tomcat的使用

    Tomcat的使用

    Tomcat下载tomcat官网:http://tomcat.apache.org安装直接将下载的tomcat压缩包解压即可*注意:此处建议不要安装在有空格或中文目录下卸载直接将解压的文件删除即可目录解析(apache开源项目通用结构)bin 可执行文件conf 配置文件lib 依赖j...

    2024-02-01 00:52:06
  • P4145 上帝造题的七分钟2 / 花神游历各国 (线段树区间开方)

    题目链接:点击这里 题目大意: 给定一个长度为 nnn 的序列 a1,a2,...,ana_1,a_2,...,a_na1,a2,...,an ,对序列进行区间开方和区间查询 题目分析: 因为 1≤a...

    2024-02-01 00:51:59
  • 使用标准输出流(system.out)和打印流 (PrintWriter)来读取txt文件

    在电脑某盘根目录下放一个文本文件.里面写一首诗(内容随意发挥).把诗的内容输出到控制台. 要求: 1.使用标准输出流(system.out)来做。 2.使用打印流; (PrintWriter)来做。 import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.FileReade

    2024-02-01 00:51:29