下列排序方法中，最坏情况下比较次数最少的是______。

admin2009-09-28 75

问题下列排序方法中，最坏情况下比较次数最少的是______。

选项 A、冒泡排序
B、简单选择排序
C、直接插入排序
D、堆排序

答案D

解析 (1)冒泡排序法：是一种最简单的交换类排序法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要比较的次数为n(n-1)/2次。(2)直接插入排序法：在直接插入排序法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，直接插入排序需要n(n-1)/2次比较。(3)简单选择排序法：对于长度为n的序列，选择排序需要扫描n-1遍，每一遍扫描均从剩下的子表中选出最小的元素，然后将该最小的元素与子表中的第一个元素进行交换。简单选择排序法在最坏情况下需要比较n(n-1)/2次。(4)堆排序法：堆排序的方法为：①首先将一个无序序列建成堆。②然后将堆顶元素(序列中的最大项)与堆中最后一个元素交换(最大项应该在序列的最后)。在最坏情况下，堆排序需要比较的次数为O(nlog₂n)。假设线性表的长度为16，那么冒泡排序、直接插入排序、简单选择排序都需要比较120次，而堆排序需要比较64次。

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

本试题收录于：二级Access题库NCRE全国计算机二级分类

二级Access

NCRE全国计算机二级

相关试题推荐

随机试题

最新回复(0)

下列排序方法中，最坏情况下比较次数最少的是______。

二级Access

NCRE全国计算机二级

有如下程序：#inc1ude＜iostream＞usingnamespacestd;c1asstest{private:inta；public:test0{cout+"cons

下面程序的运行结果是()。#include＜iostream＞usingnamespacestd；classTestClass{staticintn：public：TestClass(){n++：}staticint

使用VC++6．0打开考生文件夹下的源程序文件3．cpp。其中定义的类不完整，按要求完成下列操作，将类的定义补充完整。(1)基类People完成打印功能，定义其中的打印函数为虚函数，请在注释1后添加适当的语句。(2)类Boy继承于Peo

若有下面的函数调用：fun(a+b，3，max(n一1，b))则fun的实参个数是()。

使用VC6打开考生文件夹下的源程序文件modi3．cpp，其中定义了用于表示日期的类Date，但类Date的定义并不完整。请按要求完成下列操作，将类Date的定义补充完成。(1)定义私有数据成员year、month和day，分别用于表示年、月和日

对C++编译器区分重载函数无任何意义的信息是()。

在C++语言系统中，用于输出数据所使用的标识符cout是

在面向对象方法中，实现信息隐蔽是依靠()。

当派生类从一个基类保护继承时，基类中的一些成员在派生类中成为保护成员，这些成员在基类中原有的访问属性是()。

全回流稳定如何判断?全回流通常适用于哪些场合?

下列哪种酶不参加DNA的切除修复过程()(1999年)

气性坏疽属于

下列关于H=F×b／a=F×(M-1)叙述，错误的是

拔牙钳喙与牙长轴平行的目的是

患者，女，59岁，因支气管哮喘发作急诊入院，护士治疗时，未按操作要求，快速静脉推注某药后，患者出现头晕、心悸、血压剧降、严重的心律失常、抽搐，此药物可能是

乙工业企业销售产品每件230元，若客户购买达到100件及以上的，可得到20元／件的商业折扣。某客户2010年12月10日购买该企业产品200件，则乙工业企业因该项销售应确认的收入为（）元。

瞬时记忆的特点是()。

探月工程

张珊喜欢喝绿茶，也喜欢喝咖啡。他的朋友中没有人既喜欢喝绿茶，又喜欢喝咖啡，但他的所有朋友都喜欢喝红茶。如果上述断定为真，则以下哪项不可能为真?