首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有一种简单的排序算法,叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表
有一种简单的排序算法,叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表
admin
2019-08-01
29
问题
有一种简单的排序算法,叫做计数排序(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://jikaoti.com/ti/XWGjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
西汉的主要赋税形式中,征收对象是儿童的是
对1929—1933年的世界经济危机的特点,表述不正确的是()。
在明朝中叶,农业生产发生了一件非常重要的事件——(),对于当时的食物结构产生了重大的影响
二月革命后,为俄国无产阶级革命奠定思想基础的文献是()。
洋务运动期间,军事企业主要采取的方式是()。
二战后世界经济走向统一的过程中,仍然存在着多样性,出现了“两种体系、三种国家”,下列不属于社会主义国家经济类型的是()。
西汉的主要赋税形式中,征收对象是儿童的是()。
三国时期,三国称帝的先后顺序是()。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离|w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
某计算机有五级中断L4~L0,中断屏蔽字为M4M3M2M1M0,Mi=1(0≤i≤4)表示对Li级中断进行屏蔽。若中断响应优先级从高到低的顺序是L4→L0→L2→L1→L3,则L1的中断处理程序中设置的中断屏蔽字是____。
随机试题
胎盘早剥
黑色素瘤是
关于跨细胞膜物质转运,氧和二氧化碳气体分子转运属于
女性,32岁。较长期用药治疗后发现有浮肿、乏力、血压偏高。停药后,全身更加不适,肌无力、低血糖、血压偏低等情况,患者停用的是
两相干波源,频率为100Hz,相位差为π,两者相距20m,若两波源发出的简谐波的振幅均为A,则在两波源连线的中垂线上各点合振动的振幅为()。
《中华人民共和国会计法》第43条对伪造、变造会计凭证、会计账簿或者编制虚假财务会计报告的处罚有()。
下列关于欺诈发行股票、债券罪立案标准的说法中,错误的是()。
鼓励市民采取绿色交通方式出行,首先要提供充足和优质的公共交通。这表明国家履行()。
Shortlyaftertheaccident,two______policemencametothespot.
Sinceancienttimesithasbeenknownthatyourwordisacausesetinmotion.Infact,theuniverseitselfisclaimedtohavee
最新回复
(
0
)