首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有一种简单的排序算法,叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不柜同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表
有一种简单的排序算法,叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不柜同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表
admin
2019-08-01
45
问题
有一种简单的排序算法,叫做计数排序(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
学硕统考专业
相关试题推荐
关于亚历山大远征,下列说法中错误的是()。
武则天时期,为了管理天山以北的广大区域而设立了()。
曾在1978年5月10日《理论动态》上发表的《实践是检验真理的唯一标准》一文,以后又在《光明日报》、《人民日报》、《解放军报》转载,这篇文章的初稿作者是()。
最早以立法形式巩固大化改新成果的法令是()。
红山文化的代表性墓葬形式为()。
IP数据报的报文格式如下图所示。在没有选项和填充的情况下,报头长度域的值为()。
在请求页式系统中,一程序的页面走向(访问串或引用串)为2,3,4,5,2,3,6,2,3,4,5,6,设分配给该程序的存储块数为m。试分别计算m=3和m=4时,FIFO和LRU两种替换算法的缺页(页故障)数,并给出:结果说明了什么?
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
分时系统里,在条件相同的情况下,通常KLT(内核级线程)比ULT(用户级线程)得到更多的CPU时间,请简要解释之。
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,则最后一个结点下标为k(
随机试题
伤寒的主要传播途径是
2岁男孩,生后即发现有青紫现象,久站喜蹲踞,心脏听诊可在胸骨左缘第2肋间闻及Ⅱ级喷射性杂音,肺动脉第二音减低。
山楂的主要化学成分苦杏仁的有效成分
关于冲突规范和准据法,下列哪一判断是错误的?
()对于项目的成败具有决定性的作用。
跳槽:指人们离开原来的职业或单位到别的单位或改变职业。根据这个定义,下列哪些行为是典型的跳槽?()
(2013广东)小陈家住在5楼,他每天上下楼各一次,共需走120级楼梯。后来小陈家搬到同一栋楼的8楼,如果每层楼的楼梯级数相同,则他搬家后每天上下楼一次共需走楼梯多少级?
Whatshapesmoralemotionsinthefirstplace?Theanswerhaslongbeenevolution,hutinrecentyearsthere’sanincreasingapp
Thepriceofabitcointopped$900lastweek,anenormoussurgeinvaluethatarrivedamidstCongressionalhearingswheretopU.
Oftenconjuringimagesofdank,smelly,mosquito-infestedwastelands,uponcloserlook,wetlandsareactuallybiologicallydiver
最新回复
(
0
)