首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有一种简单的排序算法,叫做计数排序(count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表
有一种简单的排序算法,叫做计数排序(count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表
admin
2019-08-15
65
问题
有一种简单的排序算法,叫做计数排序(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://kaotiyun.com/show/PKCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一,为重新认识三代的历史与文化奠定了基础,开辟了坦途,可称之为中国文化史的里程碑。根据所学知识回答问题:金文是指()
国民党政府宣布民盟为“非法团体”,民盟总部被迫解散的时间是()。
19世纪曾形成了以()为中心的资本主义世界经济体系;二战后,逐渐形成了以()为中心的资本主义世界经济体系。
书院制度,始于唐而盛于宋,根据所学知识。回答问题:北宋最著名的四大书院是()
西周的分封制相当发达,是西周的重要政治制度,也是西周历史的一个显著特点。根据所学知识,回答问题西周建立之后,派遣同姓贵族和异姓贵族及归顺的异族首领到各地区,建立国家以藩屏护卫周室,分别分在卫、鲁、唐、燕的贵族是()
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段,种类多,交换规模大,交换方式多。试回答问题:下列关于隋唐钱币的表述,不正确的是()
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段,种类多,交换规模大,交换方式多。试回答问题:随着商业的发展,唐朝在货币和金融方面有一些重要的进步,以下表述全面的是()
以下()协议完成了从网卡到IP地址的映射。
某浮点机字长16位,其浮点数格式为:阶码5位(含1位阶符),采用补码表示,尾数11位(含1位数符),采用补码表示,且尾数为规格化形式。已知X=0.1011000011×20.0101,Y=0.0001100000×20.1000,试求X+Y.要求写出详细的
以下关于计算机存储器件的叙述,()是不正确的。
随机试题
在真理观上坚持唯物主义,就必须承认真理具有()
水肿风水相搏型的治则是
威灵仙的主治病证不包括
某村水塘上游有一家集体造纸厂。该厂已经营近10年,污水一直排入水塘上游的河流。赵立国与余庆华合伙承包村里的水塘养虾。2009年5月,赵立国、余庆华二人向水塘投放虾苗2万尾。投放后赵、余二人精心管理,日夜看护。10天后,二人发现塘内有少量的死虾出现,当即捞起
在岩石的走向、倾斜不利于边坡稳定及施工安全的地带,路堑应该(),并采取()的措施。
县级以上人民政府公安机关,经上级公安机关批准,对严重危害社会治安秩序的突发事件,可以根据情况实行现场管制。()
党的十八届四中全会决定指出,中国特色社会主义道路、理论体系、制度是全面推进依法治国的根本遵循。这一论点的主要哲学依据是()。
(7)协议在终端设备与远程站点之间建立安全连接。
查询以字母N或O或P开头的字符串,正确的是()。
下面属于黑盒测试方法的是
最新回复
(
0
)