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

admin2009-09-28 53

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

选项 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<下标>2n)。假设线性表的长度为16，那么冒泡排序、直接插入排序、简单选择排序都需要比较120次，而堆排序需要比较64次。

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

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

二级VB

NCRE全国计算机二级

相关试题推荐

随机试题

最新回复(0)

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

二级VB

NCRE全国计算机二级

下列叙述中正确的是()。

实体联系模型是一种常用的高级上【】模型，而【】是实体联系模型中的核心。

下列命令中用于Java解释命令的是()。

下面哪些代码在Java语言中是合法的?()

一些重要的程序语言(如C语言和Pascal语言)允许过程的递归调用。而实现递归调用中的存储分配通常用()。

在Java语言的所有方法中，比较特殊的一类方法是抽象方法，它只有方法头，而没有【】。

在进行模块测试时，要为每个被测试的模块另外设计两类模块：驱动模块和承接模块(桩模块)。其中【】的作用是将测试数据传送给被测试的模块，并显示被测试模块所产生的结果。

下列叙述不属于线性链表较之线性表顺序存储结构的优点的是()。

数据的物理独立性是指当数据的【】改变时，通过系统内部的自动映象或转换功能，保持了数据的逻辑结构不变。

设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1。则T中的叶子结点数为()。

肝硬化腹水患者，突然出现腹痛、发热，T38．3℃，血白细胞计数13．2×109，腹水为混浊渗出液，腹水培养有大肠埃希菌，可诊断为

患者，男性，46岁。因黑便，伴呕吐3日入院，病前有10余年胃溃疡病史，查体：贫血貌，皮肤无黄染，左锁骨上内侧可触及质硬而固定的淋巴结。入院后为了明确诊断，首先要进行的检查应是下列哪一项

某男，45岁。憎寒壮热，头目眩晕，目赤睛痛，口苦口干，咽喉不利，胸膈痞闷，咳呕喘满，大便秘结，小便赤涩。治疗当首选

装箱单的作用主要是补充发票内容的不足，通过对包装件数、唛头、规格等填制，明确产品的包装情况，()。

运用收益法评估房地产得到的结果称为比准价值。()

亚里士多德的教育思想主要体现在

APayRiseorNot?"UnlessIgetarise.I’11haveatalkwiththeboss,HenryManley,"GeorgeStrongsaidtohimself.George

Manhasbeenstoringupusefulknowledgeabouthimselfandtheuniverseattheratewhichhasbeenspiralingupwardfor10,000y