C++实现计数排序(附完整源码)

最新推荐文章于 2025-04-04 08:37:19 发布
最新推荐文章于 2025-04-04 08:37:19 发布
阅读量1.1k 收藏 1
点赞数
分类专栏： C和C++算法完整教程 C和C++Everything教程
不予转载，严禁转载，违者必纠。
本文链接：https://blog.csdn.net/it_xiangqiang/article/details/113493817
版权
本文介绍了计数排序算法，适用于0到100之间的整数排序，具有O(n+k)的时间复杂度和O(n+k)的空间复杂度。算法包括找出最大最小值、计数、累加计数、反向填充目标数组四个步骤。并提供了完整的C++源码实现。

摘要生成于 C知道 ，由 DeepSeek-R1 满血版支持， 前往体验 >

C++实现计数排序

计数排序

计数排序基于一个假设，待排序数列的所有数均为整数，且出现在（0，k）的区间之内。
如果 k（待排数组的最大值） 过大则会引起较大的空间复杂度，一般是用来排序 0 到 100
之间的数字的最好的算法，但是它不适合按字母顺序排序人名。
计数排序不是比较排序，排序的速度快于任何比较排序算法。
时间复杂度为 O（n+k），空间复杂度为 O（n+k）

算法的步骤如下：

/*

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

计数排序完整源码

#include <iostream>
了解本专栏 订阅专栏 解锁全文 超级会员免费看
C++实现计数排序(完整源码)
2301_79366332的博客
08-24 85
该算法首先找出待排序数组中的最大值和最小值，然后创建一个计数数组count，长度为max-min+1，其中max和min为数组中的最大值和最小值。然后对计数数组进行顺序求和，并创建一个临时数组tmp，用于存储排序结果。接下来再次遍历数组中的每一个元素，将其从计数数组中减去1，得到该元素在排好序的数组中的位置，并将其存储到临时数组中。计数排序是一种非比较排序算法，它的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数，利用这一信息，就可以将x直接存放到相应的位置上。
C/C++ 计数排序Counting sort算法详解及源码
希望我的博客，能帮上你解决学习中工作中所遇到的问题
06-23 1903
计数排序的时间复杂度是O(n+k)，其中n是待排序数组的长度，k是最大的元素值。由于计数排序需要额外的辅助数组来统计元素出现的次数，因此它的空间复杂度为O(n+k)。计数排序（Counting sort）是一种非比较排序算法，适用于一定范围内的整数排序。它的基本思想是通过统计元素出现的次数来确定元素在最终排序结果中的位置。计数排序的优点是速度快，稳定性好，适用于一定范围内的整数排序。然而，计数排序的缺点是需要额外的辅助数组，且只适用于非负整数排序。
计数排序源代码C++实现
01-07
计数排序 用C++实现 简单易懂 欢迎下载
C++算法之计数排序
R_mine的博客
04-29 4106
C++算法之计数排序 文章目录C++算法之计数排序一、算法描述二、代码实现三、复杂度分析 一、算法描述 给定长度为n的序列，假设已知序列元素的范围都是[0..K]中的整数，并且K的范围比较小（例如10^6，开长度为10^6左右的int类型数组所占用的内存空间只有不到4M）。解决该问题的计数排序算法描述如下： 使用整数数组cnt统计[1..K]范围内所有数字在序列中出现的个数。 使用变量i枚举1到K，如果i出现了cnt[i]次，那么在答案序列的末尾添加cnt[i]个i。 下图是一个n=6, K=3的例
C++数据排序( 附源码 )
最新发布
C_User1024的博客
04-04 1163
原理:自左向右依次遍历,若相邻两数顺序错误,则交换两数.这样,每一轮结束后,最大/最小的数就会到最后.我在此使用了函数.
计数排序----C++
qq_42036661的博客
12-06 436
emmmC++真的有些绝望，在实现上要比Java难 计数排序： 其核心思想是选择。 温故--选排： 我们知道，选择排序是第n次选出第n大的值放在a[n-1]（数组从0开始，若为n个元素，则最后一个为a[n-1]）的位置---即数组的最大值放在a[0],第二大放a[1]...第n大在a[n-1]. 上一篇博客有写。链接：https://mp.csdn.net/postedit/845931...
C++计数排序
m0_61033277的博客
07-25 449
基数排序（英语：Radix sort）是一种非比较型的排序算法，最早用于解决卡片排序的问题。它的工作原理是将待排序的元素拆分为k个关键字（比较两个元素时，先比较第一关键字，如果相同再比较第二关键字……），然后先对第k关键字进行稳定排序，再对第k-1关键字进行稳定排序，再对第k-2关键字进行稳定排序……最后对第一关键字进行稳定排序，这样就完成了对整个待排序序列的稳定排序。...
计数排序 C++
aganghaizai的博客
08-08 602
计数排序适用的应用场景： 量大但是范围小（全省高考成绩、某大型企业数万名员工年龄的排序） 且知道范围（例如成绩满分和零分 年龄0岁到150岁） 方法： 1、创建另外一个数组用于*计数***，数组的大小则为数值范围加1 （0~100）则数组长度为100-0+1 = 101； 因为我们要用数组的索引值（下标）作为每一个数值所对应的“家”**斜体样式 正好从0开始到100； 2、接着我们遍历原数组，每次读到与计数数组的下标值一样的数值时，则对计数数组改下标所对应的数组值加1（count[ nums[0] ]+
C++counting sort计数排序(针对string)的实现算法(附完整源码)
希望我的博客，能帮上你解决学习中工作中所遇到的问题
03-19 292
C++counting sort计数排序的实现算法C++counting sort计数排序的实现算法完整源码(定义，实现，main函数测试） C++counting sort计数排序的实现算法完整源码(定义，实现，main函数测试） #include <iostream> using namespace std; void countSort(string arr) { string output; int count[256], i; for (int i = 0
C++使用Merge Sort排序计数反转的实现算法(附完整源码)
希望我的博客，能帮上你解决学习中工作中所遇到的问题
03-19 337
C++使用Merge Sort排序计数反转的实现算法C++使用Merge Sort排序计数反转的实现算法完整源码(定义，实现，main函数测试） C++使用Merge Sort排序计数反转的实现算法完整源码(定义，实现，main函数测试） #include <cassert> /// for assert #include <cstdint> /// for typedef datatype uint64_t #include <iostream> /// fo
笔记: 排序算法——计数排序（C++实现）
littleboy__的博客
04-23 1978
计数排序 计数排序伪代码 C++实现 测试 基数排序 基数排序伪代码 C++实现 测试
排序-计数排序
perye
06-30 269
计数排序简介工作原理性质稳定性时间复杂度代码实现计数排序倒序遍历的计数排序 计数排序 简介 计数排序（Counting sort）是一种线性时间的排序算法。 工作原理 计数排序的工作原理是使用一个额外的数组 CCC，其中第 iii 个元素是待排序数组 AAA 中值等于 iii 的元素的个数，然后根据数组 CCC 来将 AAA 中的元素排到正确的位置。 它的工作过程分为三个步骤： 计算每个数出现了几次； 求出每个数出现次数的 前缀和； 利用出现次数的前缀和，从右至左计算每个数的排名。 性质 稳定性 计数.
计数排序（C++实现）
mycocoo的博客
12-08 225
#include<iostream> #include<stdlib.h> using namespace std; int main() { cout << "输入数组长度:"; int length = 0; cin >> length; cout << endl; cout << "输入数组:"; int *A = new int[100]; for (int i = 0; i < length; i++)
c++计数排序
一位小学生的博客
07-27 358
c++计数排序
c++实现计数排序
Yi Sun的博客
07-02 1557
代码说明 代码是我亲自码的，调试通过的，代码中有算法思想和详细的注释，一目了然。 项目已经上传到我的github：https://github.com/yisun03/sort 项目中近期会陆续更新十种排序算法的c++实现代码以及其思想。 术语说明 1、稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。 2、非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。 3、原地排序：原地
计数排序C++实现
lzq8090的博客
04-10 856
8.计数排序计数排序的基本思想计数排序的算法步骤C++代码实现 计数排序的基本思想 计数排序是一种非比较式排序，其基本思想是以空间换时间，其对特定序列的排序时间复杂度为o（n），快于任何传统的比较式排序； 计数排序的核心在于将数值转化为键，存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数，其适用场景为：重复数较多的、在一定范围内的整数数列； 计数排序的算法步骤 获取待排序列最大元素的值（imax），申请一个大小为（imax+1）的临时数组（tmp）
C/C++ 计数排序
小嗷犬的博客
08-31 1590
计数排序是一种非基于比较的排序算法，该算法于1954年由提出。找出待排序的数组中最大和最小的元素统计数组中每个值为i的元素出现的次数，存入数组C的第i项对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n + k)（其中k是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当O(k)>......
计数排序算法——C++
净无邪博客
11-24 3560
​计数排序是时间复杂度为O(n + m)的算法，空间复杂度为O(n + m)；算法思想跟散列表哈希hash有些类似，主要是利用一段有序数组计算对应元素的下表个数，然后依次输出有数组元素进行排列。基本计数排序是不稳定算法，但是优化后计数排序是稳定算法。本文主要讲解基本计数排序和优化后计数排序。 使用条件：数组必须是整数或者能全部映射为整数，数组所有元素必须在有限较集中范围； 一、具体实现步骤 1.计算原始数组的最大值max和最小值min范围，然后创建一个长度为max--min+1的排序数组sortAr
C++实现多种排序算法的源码解析
- 对radix进行计数排序（利用计数排序稳定性的特点）。 #### 4. 堆排序(Heap Sort) 堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或...
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

源代码大师

赏点狗粮吧

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付：¥1
获取中
扫码支付

您的余额不足，请更换扫码支付或充值

打赏作者

实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值