首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有一种简单的排序算法,叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表
有一种简单的排序算法,叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表
admin
2019-08-01
49
问题
有一种简单的排序算法,叫做计数排序(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,cnt=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
,且需要另一数组空间。
解析
转载请注明原文地址:https://kaotiyun.com/show/BjCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
赋税是我国古代国家宏观管理经济的重要手段。 据此回答问题:哪位皇帝的即位首次应用了秘密立储制?()
最早以立法的形式巩固大化改新成果的法令是()。
西汉的主要赋税形式中,征收对象是儿童的是()。
红山文化的代表性墓葬形式为()。
系统阐明社会主义初级阶段理论是在()。
关于分页系统,回答下列问题:(1)在页表中,哪些数据项是为实现换页而设置的?(2)设某系统为每个作业进程分配3个内存块,某作业进程在运行访问中的轨迹为1,4,3,1,6,8,1,且每一页都是按请求装入的。问:先进先出页面置换算法(FIF
已知某32位二进制机器数为11000000000000000000000000000000,试计算在下列各种编码方式下其代表的真值。(1)原码定点小数;(2)补码定点小数;(3)反码定点小数;(4)IEEE754标准短
给定序列{3,5,7,9,11,13,15,17),(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成后的二叉排序树,并求在等概率情况下查找成功的平均查找长度。(2)按表中元素的顺序构造一棵平衡二叉树,并求其在等概率情
设某多道程序系统中有用户使用内存1000M,打印机1台。系统采用可变分区动态分配算法管理内存,而对打印机采用静态分配。假设输入输出操作时间忽略不计,采用最短剩余时间优先的进程调度算法,进程最短剩余时间相同时采用先来先服务的算法,进程调度时机选择在进程执行结
随机试题
某资产至评估时已使用5年,根据该资产技术指标,正常使用情况下,每天应工作8小时,该资产实际每天工作6.5小时(一年按360天计算)。由此计算资产利用率为
兴源公司与郭某签订钢材买卖合同,并书面约定本合同一切争议由中国国际经济贸易仲裁委员会仲裁。兴源公司支付100万元预付款后,因郭某未履约依法解除了合同。郭某一直未将预付款返还,兴源公司遂提出返还货款的仲裁请求,仲裁庭适用简易程序审理,并作出裁决,支持该请求。
评标委员会完成评标后,应当向招标人提出书面评标报告,确定中标人。()
国际上工程涉及的自愿保险包括( )等。
《建设工程监理规范》规定监理月报( ),报送建设单位和本监理单位。
A公司是甲市一家大型国有企业,是增值税一般纳税人;B公司是A公司在乙市设立的子公司,主营业务为锅炉安装,其营业收入向当地地税局缴纳营业税。A公司2002年1月发生如下业务:(1)将自己生产的利能达牌75吨新型节能环保锅炉两台,以不含税单价200万元的价格
设备自然寿命也称物理寿命,是指设备从全新状态下开始使用,直到不堪再用而予以报废的全部时间过程。设备自然寿命主要取决于()。
如果商品X对于商品Y的边际替代率MRSXY小于X和Y的价格之比PX/PY,则()。
国家宗教事务局
PrettyGoodWhenSpanishfootballclubBarcelonapaidUS$35millionforRonaldinholastsummer,theyweren’tbuyingaprett
最新回复
(
0
)