首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有一种简单的排序算法,叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不柜同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表
有一种简单的排序算法,叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不柜同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表
admin
2019-08-01
65
问题
有一种简单的排序算法,叫做计数排序(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
学硕统考专业
相关试题推荐
西汉的主要赋税形式中,征收对象是儿童的是
下列各组古代民族,其语言都属于印欧语系的是()
明清时期继续采取“重农抑商”的政策,结果导致了()。
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
某计算机采用微程序控制方式,微指令字长32位,采用字段直接编码的控制方式,共有55个微命令,可分为6个互斥组,分别包含1、3、7、8、12、24个微命令。另外,该机共有5个可判定的外部条件,采用断定方式形成后续微指令地址。(1)设计该机微指令的格式,
某机字长32位,它的存储容量为256MB,按字节编址,则它的寻址范围大小为()。
—棵二叉树的后序遍历序列为DABEC,中序遍历序列为DFBAC,则先序遍历序列为()。
某DRAM芯片内部存储元排列成1024.×1024的矩阵,且已知其存取周期为0.1μs,最大刷新间隔为2ms。当采用异步刷新方式时,死时间()。
某计算机系统的内存储器由Cache和主存构成,Cache的存取周期为45纳秒,主存的存取周期为200纳秒。已知在一段给定的时间内,CPU共访问内存4500次,其中340次访问主存。问:(1)Cache的命中率是多少?(2)CPU访问内存的平均
当系统发生抖动(thrashing)时,可以采取的有效措施是____。I.撤销部分进程Ⅱ.增加磁盘交换区的容量Ⅲ.提高用户进程的优先级
随机试题
所谓相对真理就是包含谬误的真理。
朝鲜停战协议签订于()
小建中汤与补中益气汤均可用治
再生障碍性贫血的治疗中,下列属于促进造血的药物是
A、癌细胞团中可见角化珠B、癌细胞团漂浮在粘液中C、粘液将癌细胞核推向一侧D、癌细胞排列成条索状E、癌细胞形成乳头印戒细胞癌的组织学表现是
静压碾压的作用力是( )。
对品行有问题或学习有困难学生,学校不得()学生。
新闻媒介是沟通社会与政府的重要桥梁,在政务信息传输系统中具有_________的作用。但体制转型的压力,加之巨大利益的诱惑及制度缺失,给记者的职业操守带来巨大_________,各种虚假报道不时见诸报端,成为小道消息的渊薮。因此我们必须不断完善新闻从业人员
TwinstoImpairedFertilityofWomenAwomanwithatwinbrotherhasfewerchildren.Twinbrotherscanleavequiteanimpres
Whoissuestheannouncement?Whowillbethenewvicepresidentofthecompany?
最新回复
(
0
)