若要求对大小为n的数组进行排序的时间复杂度为O(nlog2n)，且是稳定的(即如果待排序的序列中两个数据元素具有相同的值，在排序前后它们的相对位置不变)，则可选择的排序方法是______。

admin2021-01-11 51

问题若要求对大小为n的数组进行排序的时间复杂度为O(nlog₂n)，且是稳定的(即如果待排序的序列中两个数据元素具有相同的值，在排序前后它们的相对位置不变)，则可选择的排序方法是______。

选项 A、快速排序
B、归并排序
C、堆排序
D、冒泡排序

答案B

解析本题考查数据结构基础知识。
快速排序、归并排序、堆排序是时间复杂度为O(nlog₂n)的排序方法，冒泡排序的时间复杂度是O(n²)。
快速排序的过程主要是划分操作，划分是以基准元素为界，从序列的两端向中间扫描，将大于基准元素者往后端移动(或交换)，不大于基准元素者向前端移动(或交换)，移动元素时不考虑所涉及两个位置之间的其他元素，这样就不能保证序列中两个相同元素的相对位置不变，也就是说快速排序是不稳定的排序方法。
堆排序是要求序列中a_i，a_2i，a_2i+1这三个元素满足a_i最小(小顶堆)或最大(大项堆)，若不满足，则通过交换进行调整，这样，在a_i与a_2i之间若有相等的两个元素，则交换后就不能保证它们的相对位置，所以堆排序是不稳定的排序方法。
归并排序是稳定的排序方法。

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

本试题收录于：软件评测师上午基础知识考试题库软考中级分类

软件评测师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

若要求对大小为n的数组进行排序的时间复杂度为O(nlog2n)，且是稳定的(即如果待排序的序列中两个数据元素具有相同的值，在排序前后它们的相对位置不变)，则可选择的排序方法是______。

软件评测师上午基础知识考试

软考中级

(2012年下半年)系统集成商Simple公司与生产型企业Perfect签订了一份企业MIS(管理信息系统)开发合同，合同已执行到设计和开发阶段，由于Perfect企业内部组织结构调整，可能会影响核心业务的流程。集成商Simple公司提出建议

在软件质量管理过程中，(12)的目的是提供软件产品和过程对于可应用的规则、标准、指南、计划和流程的遵从性的独立评价。

进口电梯的安装使用维护说明书为复印件时必须加盖()。

三大合成材料橡胶、塑料、纤维基本上都是由自由基型聚合反应完成。

一批道路厚度检查结果分别为29cm、32cm、31cm、30cm、31cm、28cm、29cm，这批厚度检查结果的极差为()cm。

在净化工艺中，离心式煤气鼓风机提高经济性能的常用方法为()。

根据借贷记账法的记账规则，下列不可能发生的是()。

阅读下面这篇公文，回答下列问题。教育部关于公布《高等学校信息公开事项清单》的通知教办函[2014]23号各省、自治区、直

下列没有歧义的一项是()。

下列政治思想或活动，打破保守，顺应当时时代潮流的是：

简述标准参照测验的项目分析。