试题-在排序方法中，元素比较次数与元素的初始排列无关的是（）

题目

在排序方法中，元素比较次数与元素的初始排列无关的是（）

A.Shell 排序

B.归并排序

C.直接插入排序

D.选择排序

上一题 下一题

解答

正确答案是 D

A、C肯定不选的，归并排序的在merge中是跟序列有关，如果有序，比较次数最少n/2，最糟是元素错落n-1。而选择排序比较次数与关键字的初始状态无关，总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。所以应该是选择排序！

C 11条回复评论

杨微粒

这题有够坑的，老是错

发表于 2025-08-05 21:00:00

0 0

望岳

比之前听的课更好懂

发表于 2021-09-12 11:35:00

0 0

云散兮

云里雾里地听完了……

发表于 2021-09-11 10:00:00

0 0

墨色槐

我想咨询一下产品经理对技术的要求有多高呢？请问数据科学专业投递平台型产品经理是否合适呢？我是海外留学生，并没有相关的产品实习经验，本科时期的实习经历也很少，都是会计师事务所的事情，感觉对这个岗位应聘没有任何帮助。由于今年疫情原因现在还在国外也没办法回去进行实习，现在秋招就快开始了真的很焦虑了

发表于 2021-09-09 19:25:00

0 0

咸鱼王

c：逆序时，时间复杂度为O(N)

d:他一定会从头到尾比较一次的，所以O(N*N)

b:有序数列，可以减少比较次数

a:如果选择增量为1，则只需要一n比较。这个欢迎补充，说得不好

发表于 2018-10-13 14:26:13

0 0

岁月长歌

归并排序中的merge是

int[] temp=new int[e-s+1];

int k=0;

while(i<=m&&j>m){

if(arr[i]>arr[j]){

temp[k++]=arr[j--]

}else{

temp[k++]=arr[i++]}

}

如果前部分的首元素大于后部分的最后元素要大，那么只需要比较n/2，即可完成排序

发表于 2018-10-13 14:26:00

0 0

子不语

说起归并算法，我不说概念性的东西。举个例子就可以看出来了

原数列：6 202 100 301 38 8 1

第一次：{6 202 }，{100 301}，{8 38}，{1} 比较3次 6和202 100和301 38和8

第二次：{6 100 202 301}，{1 8 38} 比较4次 6和100 100和202 202和301 1和8

第三次：{1 6 8 38 100 202 301} 比较4次 1和6 6和8 8和100 38和100

则总共比较次数是 3+4+4=11次

如果序列是 1 6 8 38 100 202 301

第一次：{1 6}，{8 38}，{100 202}，{301} 比较3次

第二次：{1 6 8 38}，{100 202 301} 比较4次

第三次：{1 6 8 38 100 202 301} 比较4次

总共11次

如果序列是 301 202 100 38 8 6 1

第一次：{202 301}，{38 100}，{6 8}，{1} 比较3次

第二次：{38 100 202 301}，{1 6 8} 比较3次

第三次：{1 6 8 38 100 202 301} 比较3次

总共是9次

则可以说明归并排序的比较次数和序列的初始顺序有关

发表于 2018-10-13 14:25:42

0 0

冬季恋歌

直接插入排序很明显，在完全有序的情况下每个元素只需要与他左边的元素比较一次就可以确定他最终的位置；

折半插入排序，比较次数是固定的，与初始排序无关；

快速排序，初始排序不影响每次划分时的比较次数，都要比较n次，但是初始排序会影响划分次数，所以会影响总的比较次数；

归并排序在归并的时候，如果右路最小值比左路最大值还大，那么只需要比较n次，如果右路每个元素分别比左路对应位置的元素大，那么需要比较2*n-1次，所以与初始排序有关。

发表于 2018-10-13 14:25:12

0 0

人间喜剧

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。

发表于 2018-10-13 14:24:55

0 0

资深90后

选择排序无视队列原来是否有序，他自己都会再排一遍，所以它的时间复杂度一直是最差的O（n2），最好情况和最差情况一样

发表于 2018-10-13 14:24:45

0 0

问题信息

分类：数据结构 - 简单选择排序

难度:

最新校招难题刷题，快来进刷题群吧