有一种简单的排序算法，叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不柜同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表

admin2019-08-01 71

问题有一种简单的排序算法，叫做计数排序(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；i2次。简单选择排序算法比本算法好。简单选择排序的比较次数是n(n一1)／2，且只用一个交换记录的空间；而这种方法的比较次数是n²，且需要另一数组空间。提示：此题考查的知识点是计数排序思想。因题目要求“针对表中的每个记录，扫描待排序的表一趟”，所以比较次数是n²次。若限制“对任意两个记录之间应该只进行一次比较”，则可把以上算法中的比较语句改为： for(i=0；i

解析

转载请注明原文地址:https://www.kaotiyun.com/show/ojCi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

在下面哪本著作中以异化劳动理论的形式阐述了一种新的科学世界观的雏形?()

第二次工业与第一次工业革命相比较，其新特点是()。①科学和技术真正结合起来②第二次工业革命几乎同时发生在几个先进的资本主义国家③与第一次工业革命交叉进行④使社会第一次分裂为工人阶级和资产阶级

()时，为补充兵力，开拓财源，“料民于太原”(今山西西南部)。料民就是清查民数，以便于征兵，结果引起奴隶和平民的反抗。这表明西周王朝已失去了对社会的控制力量。

提出“天有常道，地有常数”，“制天命而用之”的思想家是()。

红山文化的代表性墓葬形式为()。

格拉古兄弟改革

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。

已知在二叉树中，T为根结点，p和q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。

肺水肿二尖瓣狭窄左房衰竭期

根据《环境影响评价技术导则一总纲》，未制定专项环境影响评价技术原则的，根据建设项目（）确定环境影响评价范围。

直线职能制是最常见的组织结构类型之一。直线职能制组织结构的缺点有()。

性格是个体对现实的态度，及其相应的行为方式中表现出来的稳固而有核心意义的心理特征，主要受后天因素的影响，因而没有好坏之分。()

假如你走上新的工作岗位后。发现分管处室的同志有的踏实敬业。但缺乏开拓创新的精神；有的工作干劲大。但平时对自己要求不严；还有的工作认真。但缺乏大局观念，你将如何带好这支队伍?

领导的阶级和政党，要实现自己对于被领导的阶级、阶层、政党和人民团体的领导，必须具备的条件有()。

下列选项中，能缩短程序执行时间的措施是____。I．提高CPU时钟频率Ⅱ．优化数据通路结构Ⅲ．对程序进行编译优化

在学生表中要查找所有年龄大于30岁姓王的男同学，应该采用的关系运算是（）。

THEFIVE—SEVENSHIFT1Allmajortheoriesofchildpsychologystatethatchildrenundergoamajorchangebetweentheagesoff

计算机408

学硕统考专业

在下面哪本著作中以异化劳动理论的形式阐述了一种新的科学世界观的雏形?()

第二次工业与第一次工业革命相比较，其新特点是()。①科学和技术真正结合起来②第二次工业革命几乎同时发生在几个先进的资本主义国家③与第一次工业革命交叉进行④使社会第一次分裂为工人阶级和资产阶级

()时，为补充兵力，开拓财源，“料民于太原”(今山西西南部)。料民就是清查民数，以便于征兵，结果引起奴隶和平民的反抗。这表明西周王朝已失去了对社会的控制力量。

提出“天有常道，地有常数”，“制天命而用之”的思想家是()。

红山文化的代表性墓葬形式为()。

格拉古兄弟改革

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。

已知在二叉树中，T为根结点，*p和*q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。

肺水肿二尖瓣狭窄左房衰竭期

根据《环境影响评价技术导则一总纲》，未制定专项环境影响评价技术原则的，根据建设项目（）确定环境影响评价范围。

直线职能制是最常见的组织结构类型之一。直线职能制组织结构的缺点有()。

性格是个体对现实的态度，及其相应的行为方式中表现出来的稳固而有核心意义的心理特征，主要受后天因素的影响，因而没有好坏之分。()

假如你走上新的工作岗位后。发现分管处室的同志有的踏实敬业。但缺乏开拓创新的精神；有的工作干劲大。但平时对自己要求不严；还有的工作认真。但缺乏大局观念，你将如何带好这支队伍?

领导的阶级和政党，要实现自己对于被领导的阶级、阶层、政党和人民团体的领导，必须具备的条件有()。

下列选项中，能缩短程序执行时间的措施是____。I．提高CPU时钟频率Ⅱ．优化数据通路结构Ⅲ．对程序进行编译优化

在学生表中要查找所有年龄大于30岁姓王的男同学，应该采用的关系运算是（）。

THEFIVE—SEVENSHIFT1Allmajortheoriesofchildpsychologystatethatchildrenundergoamajorchangebetweentheagesoff

已知在二叉树中，T为根结点，p和q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。