首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内部排序中，通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对于冒泡排序算法的复杂性是(43)。
在内部排序中，通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对于冒泡排序算法的复杂性是(43)。
admin
2009-02-15
42
问题
在内部排序中，通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对于冒泡排序算法的复杂性是(43)。
选项
A、O(n
2
)
B、O(nlog
2
n)
C、O(log
2
n)
2
D、O(n
2
log
2
n)
答案
A
解析
冒泡排序的过程是先将第1个数与第2个数相比较，若为逆序则交换两数，然后比较每两个数与第三个数，依此类推，直到第n-1个数与第n个数进行过比较为止。上述过程称为一趟冒泡排序，结果是最大的数被排在了最后。然后进行第二趟排序，对前面n-1个数进行冒泡排序，结果是次大的数被排到了n-1的位置上。一般来说，第i趟冒泡排序是从第一个数到第n-i+1的位置上，整个排序过程需进行A(1≤k≤n)趟。分析冒泡排序的效率，若初始序列为正序，则只进行一次排序。在排序过程中只进行n-1次比较，不交换数据。若为逆序，则需进行n-1趟排序，需进行n(n-1)/2次比较，交换数据的数量组也相同。因此，冒泡排序的复杂性是O(n
2
)。快速排序是对冒泡排序的一种改进，其基本思想是通过一趟排序将待排序的数据分成两部分，其中一部分的关键字均比另一部分的关键字小，然后再对这两部分分别进行快速排序，最后达到整个序列有序。因此，快速排序的复杂是O(nlog
2
n)。
转载请注明原文地址:https://kaotiyun.com/show/vJjZ777K
本试题收录于：
程序员上午基础知识考试题库软考初级分类
0
程序员上午基础知识考试
软考初级
相关试题推荐
IIS安装的硬盘分区最好选用NTFS格式，是因为(1)。①可以使用操作系统的文件加密系统(EFS)对文件或文件夹进行加密②可以针对某个文件或文件夹给不同的用户分配不同的权限③可以防止网页中的Applet程序访问硬盘中的文件④
该校园网的部分区域部署了无线网络(WLAN)，采用符合IEEE802.11g标准的无线网络设备，该校园网无线网络部分的最大数据传输速率为(1)。A．11Mb/sB．54Mb/sC．100Mb/sD．108Mb/s
为了将公司内所有的计算机连接起来。图1-1中的A处可采用哪两种类型的设备?该公司在服务器上安装了DNS，以便把公司主页发布到Internet上。请问DNS的主要功能是什么?
阅读以下关于Linux系统中域名系统(DNS)的说明，回答问题1至问题4。【说明】DNS是一种TCP/IP的标准服务，负责IP地址和域名之间的转换。在Linux系统中，DNS可以由BIND(BerkeleyInternetNameDomai
该商务网站有一个购物车模块，购物车模块中自定义的两个Session属性如下。①CID用来记录用户选择的商品。②CNUM用来记录相应商品的数量。请根据表6-23所列的购物情况，将(1)～(3)空缺处对session对象处理方式的内容填
在以太网的帧结构中，帧首定界符的长度为一个字节，其值为(45)。当以太网中数据传输率提高时，帧的传输时间要求按比例缩短，这样有可能会影响到冲突检测。为了能有效地检测冲突，应该(46)。当收发两站相距S，光速为C，网络的传输速率为R，发送站的物理层时延为tP
某计算机中采用48×48数字化点阵字模表示一个汉字，字模中的每一个点在存储器中用一个二进制位存储。那么，现有1024个汉字需要在计算机中存储，则要求的存储空间应为(5)K字节。
设机罪码的长度为8位，已知X、Z为带符号的纯整数，Y为带符号的纯小数，[X]原+[Y]补+[Z]移=11111111，求出X、Y、Z的十进制真值为：X=(16)，Y=(17)，Z=(18)。
阅读以下说明和流程图，回答问题1至问题3。[说明]信息处理过程中经常需要将图片或汉字点阵做旋转处理。一个矩阵以顺时针方向旋转90°后可以形成另一个矩阵，如下图所示：流程图2-1描述了对n*n矩阵的某种处理。流程图2-2是将
随机试题
关系模式R＜u＞中，X、Y、Z是U的子集。下列关于多值依赖描述中，正确的是________。
个案分析法
A．真热假寒B．真寒假热C．上寒下热D．上热下寒症见四肢凉甚至厥冷，神识昏沉，面色紫暗，胸腹灼热，口鼻气灼，口臭息粗，小便短黄，舌红苔黄而干，脉有力，证属
A．脑立清与六味地黄丸同用B．大活络丸与通宣理肺丸同用C．乌鸡白凤丸与六君子丸同用D．胆乐胶囊与苏合香丸同用E．舟车丸与四君子丸同用提高主药功效的是()。
均衡化生产是看板管理和准时化生产方式的重要基础。()
教师在上“爱护植被、绿化祖国”一课前，安排学生课前通过收集报纸、纪录片等有关环境被污染，绿色植被被破坏的资料，通过这样的活动可以帮助学生很好地理解所学内容。这利用的课程资源是()。
将课程分为必修课程与选修课程，这是()划分的。
请认真阅读下列材料。并按要求作答。春夜喜雨【唐】杜甫好雨知时节，当春乃发生。随风潜入夜，润物细无声。野径云俱黑，江船火独明。晓看红湿处，花重锦官城。请根据上述材料回
BoeingCo’sSonicCruiser,aproposedfasterairliner,wouldbemostlyblendedmaterial,programdirectorWaltGillettesaidrec
Mosthistorianssaythatthebeginningofthemodemcivilrights【B1】______intheUnitedStateswasDecember1,1955.Thatwast
最新回复
(
0
)
