首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有一种简单的排序算法,叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表
有一种简单的排序算法,叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表
admin
2019-08-01
52
问题
有一种简单的排序算法,叫做计数排序(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
学硕统考专业
相关试题推荐
武则天时期,为了管理天山以北的广大区域而设立了()。
赋税是我国古代国家宏观管理经济的重要手段。 据此回答问题:哪位皇帝的即位首次应用了秘密立储制?()
洋务运动期间,军事企业主要采取的方式是()。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
请利用队列的基本操作写出判定一棵二叉树是否为完全二叉树的算法。要求以二叉链表作为二叉树的存储结构。函数原型为:intIsFull_Bitree(BitreeT)。
已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。
假设在一台单处理机上执行如下表所示的进程,且假定这些进程在时刻0以1,2,3,4,5的顺序创建。时间单位为时间片,优先级以数值大者为优。(1)请说明分别使用FCFS、RR(时间片=1)、SPF以及非抢夺式优先级调度算法时,这些进程的执行
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,则最后一个结点下标为k(
在一棵度为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,则树T的叶结点个数是____。
随机试题
阿司匹林为
背景资料:某二级公路的主要工序见下表。施工单位编制了如下图所示的网络计划。施工中发生了如下事件。事件一:由于施工单位设备故障,导致C工作中断4d。事件二:由于百年一遇的冰雪灾害,导致D工作晚开工15d。
成本控制的实施按照时间阶段不同,可以分为事先控制、事中控制和事后控制三阶段。其中事先控制主要是指预算编制过程中的控制。下列选项中属于预算编制中应注意的问题有()
目标手段相互依赖理论认为,个人的行为目标或手段与他人的行为目标或手段之间,如果存在相互依赖关系,其间就会发生相互作用,形成合作、竞争和______三类目标结构。
以下教育论点与孔子无关的是()。
你有一个朋友,他有赌博的嗜好,在得知你有一笔钱后,他向你借钱,你怎么办?
Thegovernmenthaspromisedtodo______liesinitspowertoeasethehardshipsofthevictimsintheflood-strickenarea.
对数据库数据的并发控制是由数据库管理系统的_________功能模块实现的。
在数据库调优过程中,将每天的销售额明细累加后放入日销售额统计表的调优方法一般被称为()。
文档“北京政府统计工作年报.docx”是一篇从互联网上获取的文字资料,请打开该文档并按下列要求进行排版及保存操作:将标题“(三)咨询情况”下用蓝色标出的段落部分转换为表格,为表格套用一种表格样式使其更加美观。基于该表格数据,在表格下方插入一个饼图,用于
最新回复
(
0
)