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

admin2023-02-06 36

问题有一种简单的排序算法，叫作计数排序(count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为C。
设计实现计数排序的算法。对于有n个记录的表，关键字的比较次数是多少?与简单选择排序相比较，这种方法是否更好？为什么？

选项

答案[*] 对于有n个记录的表，关键字比较n²次。简单选择排序算法比本算法好。简单选择排序的比较次数是n(n-1)／2，且只用一个交换记录的空间；而这种方法的比较次数是n²，且需要另一数组空间。

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

学生的思想品德是由知、情、意、行四个因素组成的，所以德育过程必须从培养教育者的正确认识开始的。()

()主张应该关注非预期的效果，评价重点放在课程计划实际结果上，更多地关注课程计划满足实际需要的程度。

教学日记是教师对自己教学活动中具有教育价值的各种经验以及在此基础上所进行的创造性的理解和认识予以真实的书面记录和描写。常见的教学日记形式包括()。

杨毅在学习过程中，将自己的笔记本划分成两半，一半记录老师上课时所讲的内容，另一半记录自己不懂的地方或重要的地方。杨毅在这一过程中使用的学习策略属于()。

颠覆性技术具有两面性，既可能产生正面结果，也可能带来负面影响。它可能对已有的技术和市场带来革命性，，甚至改变世界力量。通常，这类技术的出现没有规律，更难以。依次填入画横线部分最恰当的一项是：

工资

司法行政管理

患儿，女，6岁。近日来大便清稀，夹有泡沫，臭气不甚，肠鸣腹痛，伴恶寒发热，鼻流清涕、咳嗽咽痒；舌质淡，苔薄白，脉浮紧，指纹淡红。中医辨病为小儿泄泻，本病证型为

关于生长发育评价方法下列哪项是错误的

某国甲公司向中国乙公司出售一批设备，约定贸易术语为“FOB(Incoterms2010)”，后设备运至中国。依《国际贸易术语解释通则》和《联合国国际货物销售合同公约》，下列哪一选项是正确的?

历史上曾经存在过()种类型的法律制度。

发起人持有的本公司股份，自公司成立之日起1年内不得转让。公司公开发行股份前已发行的股份，自公司股票在证券交易所上市交易之日起1年内不得转让。(　　)

已知全集U={1，2，3，4，5}，集合A={1，2}，B={2，3，4}，则=()

“咬定青山不放松”主要反映的意志品质是()。

有以下两个表：借阅（借书证号C,总编号C,借书日期D）图书（总编号C,分类号C,书名C,作者C,出版单位C,单价N）统计每本图书被借阅的次数，若没被借阅过，则显示次数为0，正确的SQL语句是：

计算机408

学硕统考专业

学生的思想品德是由知、情、意、行四个因素组成的，所以德育过程必须从培养教育者的正确认识开始的。()

()主张应该关注非预期的效果，评价重点放在课程计划实际结果上，更多地关注课程计划满足实际需要的程度。

教学日记是教师对自己教学活动中具有教育价值的各种经验以及在此基础上所进行的创造性的理解和认识予以真实的书面记录和描写。常见的教学日记形式包括()。

杨毅在学习过程中，将自己的笔记本划分成两半，一半记录老师上课时所讲的内容，另一半记录自己不懂的地方或重要的地方。杨毅在这一过程中使用的学习策略属于()。

工资

司法行政管理

患儿，女，6岁。近日来大便清稀，夹有泡沫，臭气不甚，肠鸣腹痛，伴恶寒发热，鼻流清涕、咳嗽咽痒；舌质淡，苔薄白，脉浮紧，指纹淡红。中医辨病为小儿泄泻，本病证型为

关于生长发育评价方法下列哪项是错误的

某国甲公司向中国乙公司出售一批设备，约定贸易术语为“FOB(Incoterms2010)”，后设备运至中国。依《国际贸易术语解释通则》和《联合国国际货物销售合同公约》，下列哪一选项是正确的?

历史上曾经存在过()种类型的法律制度。

发起人持有的本公司股份，自公司成立之日起1年内不得转让。公司公开发行股份前已发行的股份，自公司股票在证券交易所上市交易之日起1年内不得转让。( )

已知全集U={1，2，3，4，5}，集合A={1，2}，B={2，3，4}，则=()

“咬定青山不放松”主要反映的意志品质是()。

有以下两个表：借阅（借书证号C,总编号C,借书日期D）图书（总编号C,分类号C,书名C,作者C,出版单位C,单价N）统计每本图书被借阅的次数，若没被借阅过，则显示次数为0，正确的SQL语句是：

发起人持有的本公司股份，自公司成立之日起1年内不得转让。公司公开发行股份前已发行的股份，自公司股票在证券交易所上市交易之日起1年内不得转让。(　　)