2. 从业资格
  3. 若要求对大小为n的数组进行排序的时间复杂度为O(nlog2n)，且是稳定的（即如

若要求对大小为n的数组进行排序的时间复杂度为O(nlog2n)，且是稳定的（即如

资格题库2022-08-02  48
问题 若要求对大小为n的数组进行排序的时间复杂度为O(nlog2n)，且是稳定的（即如果待排序的序列中两个数据元素具有相同的值，在排序前后它们的相对位置不变），则可选择的排序方法是（39）。A.快速排序B.归并排序C.堆排序D.冒泡排序
选项 A.快速排序
B.归并排序
C.堆排序
D.冒泡排序
答案 B
解析 A.  快速排序B.  归并排序C.  堆排序D.  冒泡排序答案解析：B本题考查数据结构基础知识。
快速排序、归并排序、堆排序是时间复杂度为0（nlog2n）的排序方法，冒泡排序的时间复杂度是0（n2）。
快速排序的过程主要是划分操作，划分是以基准元素为界，从序列的两端向中间扫描，将大于基准元素者往后端移动（或交换），不大于基准元素者向前端移动（或交换），移动元素时不考虑所涉及两个位置之间的其他元素，这样就不能保证序列中两个相同元素的相对位置不变，也就是说快速排序是不稳定的排序方法。
堆排序是要求序列中ai,a2i,a2i-1这三个元素满足ai最小（小顶堆）或最大（大顶堆），若不满足，则通过交换进行调整，这样，在ai与a2i之间若有相等的两个元素，则交换后就不能保证它们的相对位置，所以堆排序是不稳定的排序方法。
归并排序是稳定的排序方法。
转载请注明原文地址:https://tihaiku.com/congyezige/2425179.html
本试题收录于： 初级程序员题库软件水平考试初中高级分类

初级程序员

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)