17)在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是( ) 。 选择排序。为什么呢？？？
在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是折半插入排序。
原因：
一、直接插入排序很明显，在完全有序的情况下每个元素只需要与他左边的元素比较一次就可以确定他最终的位置；
二、折半插入排序，比较次数是固定的，与初始排序无关；
三、快速排序，初始排序不影响每次划分时的比较次数，都要比较n次，但是初始排序会影响划分次数，所以会影响总的比较次数；
四、归并排序在归并的时候，如果右路最小值比左路最大值还大，那么只需要比较n次，如果右路每个元素分别比左路对应位置的元素大，那么需要比较2*n-1次，所以与初始排序有关。
归并排序
假设二路归并
1234
12 34 2次
2<4 2<3 2次 不用再继续 共4次
1 2 3 4 有序
2314
23 14 2次
3<4 3>1 2次 再用2比较
2>1 1次 插入
1 2 3 4 有序 共5次
可见归并排序的比较次数就不固定，随着初始状态不同而不同。
扩展资料：
一个排序算法是稳定的，就是当有两个相等记录的关键字R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。
当相等的元素是无法分辨的，比如像是整数，稳定度并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。
（4,1）（3,1）（3,7）（5,6）在这个状况下，有可能产生两种不同的结果，一个是依照相等的键值维持相对的次序，而另外一个则没有：
（3,1）（3,7）（4,1）（5,6） （维持次序)
（3,7）（3,1）（4,1）（5,6） （次序被改变)
不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地实现为稳定。
作这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个对象间之比较，就会被决定使用在原先数据次序中的条目，当作一个同分决赛。然而，要记住这种次序通常牵涉到额外的空间负担。
参考资料来源：百度百科-排序算法
可以看到，每次都是遍历一遍剩下要排序的部分，找出其最大值或最小值。所以。。。。。
不理解 所谓的关键字比较的次数 和 记录的初始排序次序 是什么意思
记录的初始排序次序 就是 排序前的状态 1 4 5 6 7 8 9 2 3 这就是初始排序次序。
关键字的比较次数，就是比较的次数，例如从大到小排序，你得进行比较，类似这样的语句：
if(a[1]<a[2]) //这里就是比较。
{
则交换两个值。
}
已赞过
已踩过<
