Question

17)在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是( ) 。 选择排序。为什么呢？？？

Answer 1

在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是折半插入排序。

原因：

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

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

三、快速排序，初始排序不影响每次划分时的比较次数，都要比较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） （次序被改变)

不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地实现为稳定。

作这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个对象间之比较，就会被决定使用在原先数据次序中的条目，当作一个同分决赛。然而，要记住这种次序通常牵涉到额外的空间负担。

参考资料来源：百度百科-排序算法

Answer 2

冒泡也与初始排序次序有关，因为一般在实现冒泡排序时，都采用改进算法，设置一个标志位flag，将其初始值设置为非0，表示被排序的表示是一个无序的表，每一次排序开始前设置flag值为0，在进行数据交换时，修改flag为非0。在新一轮排序开始时，检查此标志，若此标志为0，表示上一次没有做过交换数据，则结束排序；否则进行排序。所以，当记录序列的初始状态为"正序"，则冒泡排序过程只需进行一趟排序即可

Answer 3

答案是直接选择排序！因为不管初始排列次序是相对正序还是相对乱序，选择排序对关键字的比较次数都是相同的！因为它每一次都要选出关键字中最小的！

Answer 4

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
可以看到，每次都是遍历一遍剩下要排序的部分，找出其最大值或最小值。所以。。。。。

追问

不理解 所谓的关键字比较的次数 和 记录的初始排序次序 是什么意思

追答

记录的初始排序次序 就是 排序前的状态 1 4 5 6 7 8 9 2 3 这就是初始排序次序。
关键字的比较次数，就是比较的次数，例如从大到小排序，你得进行比较，类似这样的语句：
if(a[1]<a[2]) //这里就是比较。
{
则交换两个值。
}

追问

那冒泡也与 初始排序次序无无关ya ?

追答

若记录序列的初始状态为"正序"，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次交换，且不移动记录；反之，若记录序列的初始状态为"逆序"，则需进行n(n-1)/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。

追问

还是不懂``

追答

这个>>>>> 我也不知道怎么解释了。

Answer 5

因为选择排序每趟选择的比较次数是固定的，不会因为顺序不一样而比较次数不一样。比如（1，2，3）和（3，2，1）这两个序列次序不同，但是在第一趟选择排序中选出最小的值1同样进行2次比较，第二趟选出第二小的值2同样进行1次比较……也就是说，……