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

admin2023-02-06 34

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

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

教学过程的规律有哪些?()

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

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

一只闹钟的秒针顶点距离表盘圆心4厘米，分针顶点距离表盘圆心3厘米。小王烧开一壶水的时间内，秒针顶点累计移动了40厘米。那么这一时间段内，分针顶点与表盘圆心的连线扫过的扇形面积为多少平方厘米?

铣削三面刃铣刀端面齿时，若铣刀廓形角偏差较大，不仅会影响齿槽角，还会影响刀齿棱边宽度的一致性。()

A．视网膜电图(ERG)B．眼电图(EOG)C．吲哚青绿血管造影(ICG)D．视觉诱发电位(VEP)E．眼底荧光血管造影(FFA)反映脉络膜血管的情况

突然出现片状脱发者为

下列哪项不具备申请护士注册资格

从形式上看，企业战略联盟形式是企业间的合作，但其实质是以合作代替对抗，是更高形式的激烈竞争的开始。()

我国行业标准规定沥青面层质量检测项目有压实度、弯沉值、密度、横坡、井框与路面的高差及()八项。

单只的鞋、袜、手套属有商业价值的广告品和货样，仍要计征关税。(　　)

以下交纳印花税的证照有(　　)。

论述民国时期新军阀混战

设f(x)在[0，1]上连续，且0≤f(x)≤1，试证在[0，1]内至少存在—个ξ，使f(ξ)=ξ

计算机408

学硕统考专业

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

教学过程的规律有哪些?()

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

一只闹钟的秒针顶点距离表盘圆心4厘米，分针顶点距离表盘圆心3厘米。小王烧开一壶水的时间内，秒针顶点累计移动了40厘米。那么这一时间段内，分针顶点与表盘圆心的连线扫过的扇形面积为多少平方厘米?

铣削三面刃铣刀端面齿时，若铣刀廓形角偏差较大，不仅会影响齿槽角，还会影响刀齿棱边宽度的一致性。()

A．视网膜电图(ERG)B．眼电图(EOG)C．吲哚青绿血管造影(ICG)D．视觉诱发电位(VEP)E．眼底荧光血管造影(FFA)反映脉络膜血管的情况

突然出现片状脱发者为

下列哪项不具备申请护士注册资格

从形式上看，企业战略联盟形式是企业间的合作，但其实质是以合作代替对抗，是更高形式的激烈竞争的开始。()

我国行业标准规定沥青面层质量检测项目有压实度、弯沉值、密度、横坡、井框与路面的高差及()八项。

单只的鞋、袜、手套属有商业价值的广告品和货样，仍要计征关税。( )

以下交纳印花税的证照有( )。

论述民国时期新军阀混战

设f(x)在[0，1]上连续，且0≤f(x)≤1，试证在[0，1]内至少存在—个ξ，使f(ξ)=ξ

单只的鞋、袜、手套属有商业价值的广告品和货样，仍要计征关税。(　　)

以下交纳印花税的证照有(　　)。