首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有一种简单的排序算法,叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不柜同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表
有一种简单的排序算法,叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不柜同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表
admin
2019-08-01
62
问题
有一种简单的排序算法,叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不柜同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录,统计出的计数值为c,那么,这个记录在新的有序表中的合适的存放位置即为c。
设计实现计数排序的算法。对于有n个记录的表,关键字的比较次数是多少?与简单选择排序相比较,这种方法是否更好?为什么?
选项
答案
typedef struct{ int key: datatype info }flecType; void countSort(RecType a[],b[],int n){ //计数排序算法,将a中记录排序放入b中 int i,j,cnt; for(i=0;i
2次。 简单选择排序算法比本算法好。简单选择排序的比较次数是n(n一1)/2,且只用一个交换记录的空间;而这种方法的比较次数是n
2
,且需要另一数组空间。 提示:此题考查的知识点是计数排序思想。因题目要求“针对表中的每个记录,扫描待排序的表一趟”,所以比较次数是n
2
次。若限制“对任意两个记录之间应该只进行一次比较”,则可把以上算法中的比较语句改为: for(i=0;i
解析
转载请注明原文地址:https://kaotiyun.com/show/ojCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
罗马法的集大成《查士丁尼民法大全》产生的时间是在()。
一战后,法国对外政策的特点是()。
赋税是我国古代国家宏观管理经济的重要手段。 据此回答问题:哪位皇帝的即位首次应用了秘密立储制?()
列宁在()报告中论证了在俄国实现和平过渡的可能性和必要性。
下列选项中,属于汉武帝时期削弱地方诸侯势力的措施是()。①推恩令②左官律③附益法④酎金夺爵
在操作系统中,P,V操作是一种()。
若二叉树的前序序列为DABCEFG,中序序列为BACDFGE,则其层次序列为()。
分时系统里,在条件相同的情况下,通常KLT(内核级线程)比ULT(用户级线程)得到更多的CPU时间,请简要解释之。
某计算机的CPU主频为500MHz,CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0.5MB/s,采用中断方式与主机进行数据传送,以32位为传输单位,对应的中断服务程序包含18条指令,中断服务的其他开销相当于2条指令的执行时间
随机试题
甲、乙各携所养宠物犬散步,两犬发生厮打,甲、乙未加约束,袖手旁观。两犬在撕咬中突然窜至马路中央。正在驾车以正常速度通过的个体出租车司机丙见状紧急刹车,但因事发突然,仍将甲的宠物犬轧死。同时,车内乘客丁因紧急刹车而撞破眼镜,致眼部受伤。问:甲的宠物犬被轧
患者,女,28岁。患二尖瓣脱垂伴关闭不全8年,因不明原因发热4周,全身大关节疼痛来院。查体:体温38℃,轻度贫血貌,指甲下可见暗红色线状出血,双肺阴性,心脏不大,心率100次/分,律整,心前区及心尖部可闻及4/6级收缩期吹风样杂音,向左腋下传导,肝脾肋下均
A、盐析沉淀法B、有机溶剂沉淀法C、凝胶过滤法D、离子交换层析E、亲和层析利用一些带电离子基团的凝胶或纤维素,吸附带有相反电荷的蛋白质抗原的方法为
关于工程预付款支付的说法,正确的是()。
后续检定是计量器具首次检定后的检定,不包括()。
以下关于对计算机系统进行新硬件安装的正确描述有()。
某大学城的社区民警小周通过“周Sir有话说”微信公众号和微博,以自创诗歌、RAP说唱、微视频等多种形式,宣传防盗防骗防火等治安常识;通过开展“平安校园”创建活动,组织动员辖区学校保卫处、团委、学生会,成立校园联合义务巡逻队,加强大学城巡逻防护,实现了大学城
你有什么好的措施解决农民工子女上学问题?
阅读以下说明和C函数,填充函数中的空缺,将解答填入答题纸的对应栏内。【说明】函数Insert_key(*root,key)的功能是将键值key插入到*root指向根结点的二叉查找树中(二叉查找树为空时*root为空指针)。若给定的二叉查
对长度为n的线性表进行顺序查找,在最坏情况下需要比较的次数为()。
最新回复
(
0
)