首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有一种简单的排序算法,叫做计数排序(count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表
有一种简单的排序算法,叫做计数排序(count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表
admin
2019-08-15
38
问题
有一种简单的排序算法,叫做计数排序(count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录,统计出的计数值为c,那么,这个记录在新的有序表中的合适的存放位置即为c。
设计实现计数排序的算法。对于有n个记录的表,关键字的比较次数是多少?与简单选择排序相比较,这种方法是否更好?为什么?
选项
答案
typedef struct{ int key ; datatype info }RecType; void countSort(RecType a[],b[],int n){ //计数排序算法,将a中记录排序放入b中 int i,j,cnt; for(i=0;i<n;i++){ //对每一个元素 for(j=0,ent=0;j<n;j++) if(a[j].key<a[i].key)cnt++; //统计关键字比它小的元素个数 B[cnt]=a[i]; } } 对于有n个记录的表,关键字比较n
2
次。 简单选择排序算法比本算法好。简单选择排序的比较次数是n(n一1)/2,且只用一个交换记录的空间;而这种方法的比较次数是n
2
,且需要另一数组空间。 提示:此题考查的知识点是计数排序思想。因题目要求“针对表中的每个记录,扫描待排序的表一趟”,所以比较次数是n
2
次。若限制“对任意两个记录之间应该只进行一次比较”,则可把以上算法中的比较语句改为: for(i=0;i<n;i++)a[i].count=0; //各元素再增加一个计数域,初始化为0 for(i=0;i<n;i++) for(j=i+1;j<n;j++) if(a[i].key<a[j].key)a[j].count++; else a[i].count++;
解析
转载请注明原文地址:https://jikaoti.com/ti/BMGjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
严复翻译的《天演论》一书的出版时间是()。
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
某定点机字长8位(含1位符号位),现该机中一个寄存器的内容为43H,则将其算术左移一位、算术右移一位的结果分别为()。
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
ICMP在TCP/IP协议集中属于()。
已知某32位二进制机器数为11000000000000000000000000000000,试计算在下列各种编码方式下其代表的真值。(1)原码定点小数;(2)补码定点小数;(3)反码定点小数;(4)IEEE754标准短
就绪队列中有n个进程等待使用一个CPU,那么,如果采用不同的调用算法,就有()种调度顺序。
某路由器的IP地址是125.45.23.12,它在以太网上的物理地址为2345AB4F67CD,它收到了一个分组,分组中的目的IP地址是125.11.78.10。(1)试给出这个路由器发出的ARP请求分组中的各项目。假定不划分子网。
某计算机字长为16位,主存地址空间大小为128KB,按字编址。采用单字长指令格式,指令各字段定义如图B-4所示。转移指令采用相对寻址方式,相对偏移量用补码表示,寻址方式定义见表B-1。请回答下列问题:若操作码0010B表示加法操作(助记符为ad
随机试题
女性,60岁,因消瘦、腹胀、纳差5年入院,病前曾有慢性肝病史,查:皮肤、巩膜黄染,腹部膨隆,移动性浊音阳性,脾肋下可触及。病人突然呕吐出暗红色血块约1000ml,急诊胃镜示“食管静脉曲张破裂出血”,护士应估计病人目前最有可能先出现()
关于呼吸活瓣,下列说法错误的是
婴儿腹泻经输液脱水纠正,出现精神萎靡、腹胀、心音低钝,首先应考虑为
A.稀硝酸B.稀盐酸C.硝酸D.盐酸E.醋酸盐缓冲液铁盐检查法中检查杂质所用的酸是
下述关于民用建筑项目中对公共服务设施用房布局的说法中,错误的是:[2012-31]
坚持以人为本,以人与自然的和谐为主线,以经济发展为核心,以提高人民生活质量为根本出发点,以科技和体制创新为突破口,坚持经济社会发展与人口、资源和生态环境相协调。这是我国21世纪初可持续发展的()。
财政收入分配职能的目标是()。
下列收入属于企业所得税应税收入的有()。
正方:论据:反方
CAFTA
最新回复
(
0
)