转自: http://blog.csdn.net/pi9nc/article/details/12220851
1)算法简介
计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
2)算法描述和分析
算法的步骤如下:
1、找出待排序的数组中最大和最小的元素
2、统计数组中每个值为i的元素出现的次数,存入数组C的第i项
3、对所有的计数累加(从C中第一个元素开始,每一项和前一项相加,其实就是根据个数转换为地址)
4、反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1
当输入的元素是n 个0到k之间的整数时,它的运行时间是 O(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。
由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。例如:计数排序是用来排序0到100之间的数字的最好的算法,但是它不适合按字母顺序排序人名。但是,计数排序可以用在基数排序中的算法来排序数据范围很大的数组。
3)算法图解
我们使用计数排序对一个乱序的整数数组进行排序。
首先创建一个临时数组(长度为输入数据的最大间隔),对于每一个输入数组的整数k,我们在临时数组的第k位置"1"。如下图
上图中,第一行表示输入数据,第二行表示创建的临时数据,临时数组的下标代表输入数据的某一个值,临时数组的值表示输入数据中某一个值的数量。
如果输入数据中有重复的数值,那么我们增加临时数组相应的值(比如上图中5有3个,所以小标为5的数组的值是3)。在“初始化”临时数组以后,我们就得到了一个排序好的输入数据。
我们顺序遍历这个数组,将下标解释成数据, 将该位置的值表示该数据的重复数量,记得得到一个排序好的数组。
4)算法代码
#include <stdlib.h> #include <string.h> #include <stdio.h> /************************************************************** 功能:计数排序。 参数: data : 要排序的数组 length :数组元素的个数 maxValue :数组中元素数组最大值 +1 (这个需要+1,因为数组索引从0开始) 返回值: 成功0;失败-1. *************************************************************/ int ctsort(int *data, int length, int maxValue) { int * counts = NULL,/*计数数组*/ * temp = NULL;/*保存排序后的数组*/ int i = 0; /*申请数组空间*/ if ((counts = (int *) malloc( maxValue * sizeof(int))) == NULL) return -1; if ((temp = (int *) malloc( length * sizeof(int))) == NULL) return -1; /*初始化计数数组*/ for (i = 0; i < maxValue; i ++) counts[i] = 0; /*数组中出现的元素,及出现次数记录*/ for(i = 0; i < length; i++) counts[data[i]] += 1; /*调整元素计数中,加上前一个数,其实就是将之前存放的个数转换为地址 */ for (i = 1; i < maxValue; i++) counts[i] += counts[i - 1]; /*使用计数数组中的记录数值,来进行排序,排序后保存的temp*/ for (i = length -1; i >= 0; i --){ temp[counts[data[i]] - 1] = data[i]; /*从最后一个元素开始找其应该存放的位置*/ printf("temp[%d]:%d\n",counts[data[i]] - 1,temp[counts[data[i]] - 1]); //查看一下temp数组 counts[data[i]] -= 1; } memcpy(data,temp,length * sizeof(int)); free(counts); free(temp); return 0; } int main() { int a[8] = {2,0,2,1,4,6,7,4}; int max = a[0], i = 0; /*获得数组中中的数值*/ for ( i = 1; i < 8; i++){ if (a[i] > max) max = a[i]; } ctsort(a,8,max+1);//因为数组索引从0开始,所以要加1 for (i = 0;i < 8;i ++) printf("%d\n",a[i]); }
相关推荐
有界面,对随机产生的10个数进行排序并输出结果;计数排序、冒泡排序、快速排序;运用了继承和向上转型
在传递给函数之前,nums 在预先未知的某个下标 k(0 )上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在...
leetcode有效期 LeetCode-practice LeetCode ...计数排序 常用 LRU缓存淘汰算法 leetcode题 入门以及简单级题: 两数之和 两数相加 整数翻转 回文数 罗马数字转整数 排队问题 公共前缀 有效括号 二进制求和
StructuriDeDate_Tema1 在以下网址实施工具: 气泡排序 快速排序 快速排序-随机旋转 快速排序-Pivot Mediana DIN 3 合并排序 计数排序 基数排序-LSD-înbaza 10
计数排序 桶排序 二叉树 顺序遍历 层次遍历 左右翻转 最大值 最大深度 最小深度 平衡二叉树 链表 删除节点 翻转链表 中间元素 合并两个已排序链表 链表排序 归并排序 快速排序 两个链表是否相交 栈&队列 带最小值...
计数排序 1365 有多少小于当前数字的数字 1122 数组相对排序 注:固定数字用桶排序!!!! 二分法 33 搜索旋转排序数组 排列问题 37 下一个排列 贪心 1402 做菜顺序 链表排序 147 冒泡排序 148 归并排序
计数排序 气泡排序 气泡排序的巧妙用例 基数排序 二进制搜索树 AVL树 哈希表 哈希表代码 链表 二元搜寻 实践问题 在经过排序和旋转的数组中搜索元素 插值搜索 查找最小/最大的Kth 在数组中查找对 快速排序 检测图中...
计数排序 堆排序 基数排序 搜索算法 线性搜寻 二元搜寻 插值搜索 数组中的第二个Max 在矩阵上进行二进制搜索 数数X的数组 如果阵列顺时针旋转,则查找最小值 反转对 找出a,b使a + b = X 合并后找到两个排序数组的...
软件设计 《软件设计与开发实践I》课程代码内容: 第 3 周1.1 跳过列表1.2 公里1.3 优先队列1.4 三元素元组 第 5 周2.1 线程化二叉树2.2森林...第 13 周4.1快速排序4.2线性排序4.2.1计数排序4.2.2基数排序4.2.3桶分类
计数排序 桶排序 随机排列 最大子数组 分治求解 动态规划求解 选择算法 栈和队列 双向链表 开放寻址法 二叉搜索树 红黑树 动态规划(钢条切割最大收益) 赫夫曼树 B树 图的遍历 最小树生成 最短路径 求两个字符串的...
计数排序 基数排序 查找 有序数组的二分查找 插值查找 模糊二分查找 散列表 支持插入、删除、查找的散列表 分离链接法处理散列表中的冲突 线性探查法处理散列表中的冲突 二叉树 二叉树的前、中、后序以及层次遍历 ...
计数排序 基数排序 荷兰国旗问题(partition) 最小和问题(MergeSort) 逆序对个数问题(MergeSort) 常用算法 LRU算法实现:leetcode145题 表达式求值:中缀表达式转后缀表达式求值 树形DP 给定一颗二叉树的头节点...
3-计数排序 基本算法 4-最大成对乘积 5-十进制到二进制转换 6-最大公约数 7-最低公倍数 线性数据结构 8-堆栈实现 9-平衡支架检查 10-表达式解析器 11-队列实施 12-链表的实现 13-通过链接列表进行堆栈 14-通过链接...
4、从DATA_BUF(1000H)开始存放50个字节数据,编写程序将这些数据由小到大排序,排序后的数据仍放在该区域中。 要求原始数据在源程序中给出,排序前后的数据以每行10个的格式显示在屏幕上。 5、测量一字符串长度,并用...
说明:T2工作在连续增计数模式;其工作频率为Fcpu/8=5MHz;禁止比较 2)T2PR:#0C8H 说明:因为采样频率为25kHz,其采样周期为40us,而T2的记数频率为5 所以其计数值为:T2PR/25k=200=C8H 3)GPTCONA:#441H 说明:允许...
改进的速度规范化将改善转场的质量(225行python代码..在Ubuntu上测试)结果五个小时的高能量音乐,可进行长时间编码,驾驶,运动或学习: :发现可以使用相关性对齐具有相同速度的技术片段,以实现平稳过渡关联不...
Leetcode / Lintcode-Python 这是我的python的leetcode解决方案介绍二元搜寻62.在旋转排序数组中搜索140.Fast Power 428.Pow(x,n) 845.最大公约数39.恢复旋转排序数组8,旋转...三角计数609.Two Sum-小于或等于目
范围总和的计数(硬) - 排序数组中的单个元素(中) - 在旋转排序数组中找到最小值(中) - 在旋转排序数组 II (中)中搜索- 在旋转排序数组中搜索(中) - 查找排序数组中元素的第一个和最后一个位置(中) - ...
//计数排序 for( i=0;i;i++) q[i]=0;//把数组元素全部赋初值为0 for( i=0;i;i++) q[t[i]]+=1;//判断累计相同等待时间的个数 q[t[i]]=q[t[i]]+1; for( i=1;i;i++) q[i]+=q[i-1];//q[i]=q[i]+q[i-1] for( i...
谭浩强教授,我国著名计算机教育专家。1934年生。1958年清华大学毕业。学生时代曾担任清华大学学生会主席、北京市人民代表。他是我国计算机普及和高校计算机基础教育开拓者之一,现任全国高等院校计算机基础教育研究...