首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下列排序方法中,最坏情况下比较次数最少的是______。
下列排序方法中,最坏情况下比较次数最少的是______。
admin
2009-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
2
n)。假设线性表的长度为16,那么冒泡排序、直接插入排序、简单选择排序都需要比较120次,而堆排序需要比较64次。
转载请注明原文地址:https://kaotiyun.com/show/bIwp777K
本试题收录于:
二级Access题库NCRE全国计算机二级分类
0
二级Access
NCRE全国计算机二级
相关试题推荐
在线性表的顺序存储结构中,其存储空间连续,各个元素所占的字节数
若有表达式“(w)?(--x):(++y)”,则其中与w等价的表达式是()。
假定int类型变量占用两个字节,其有定义intx[10]={0,2,4};,则数组x在内存中所占字节数是()。
在函数中,定义一个变量时,默认的存储类型是
下列C++流的操作符中,能够设置下一个数据的输出宽度的是
已知数组arr的定义如下:intarr[5]={1,2,3,4,5};下列语句中输出结果不是3的是
下列各序列中不是堆的是()。
以下关于卞索引和候选索引的叙述正确的是
报表由______、______、______、页面页脚和报表页脚等5节组成。
Access窗体中的文本框控件分为______。
随机试题
操作系统为用户提供两类使用接口:一是程序员接口;二是_______。
函数y=arcsin的定义域为()
试述传染性非典型肺炎的传播途径及临床特征。
患儿男,9岁。水肿、血尿10天,进行性少尿8天,10天前晨起发现双眼睑水肿,尿色发红。8天前尿色变浅,但尿量进行性减少,查体:体温36.9℃,呼吸24次/分,血压145/80mmHg,发育正常,营养中等,重病容,精神差,结膜稍苍白,巩膜无黄染。化验尿蛋白(
在膜剂中起增塑剂作用的为在膜剂中起着色剂作用的为
《地下水质量标准》(GB/T14848—93)依据我国地下水水质现状、人体健康基准值及地下水质量保护目标,并参照了生活饮用水、工业、农业用水水质最低要求,将地下水质量总共划分为五类,其中( )地下水以农业和工业用水要求为依据,除适用于农业和部分工业用
针对审计报告及相关内容,以下说法中,正确的有()。
【马端临】北京师范大学2003年中国史学史真题;南京大学2005年中国古代史真题
Scientistsbelievetheyhavesolvedoneoftheenduringmysteriesofthesexes--whymencandrinkmorealcoholthanwomen.Many
NelsonMandelawasstillinjailwhenthefirststreetwasnamed【67】him.BythetimeheretiredasPresidentofSouthAfrica,hu
最新回复
(
0
)