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

Question

在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是(    )。
A. 希尔排序    B. 冒泡排序    C.插入排序    D.选择排序
我只知道应该选择B或D，但是答案是D，谁能告诉我为什么？？？！！！

Answer 1

我认为选D。插入排序（此处包括直接插入排序、折半插入排序、希尔排序）中，每一趟排序时，关键字比较次数和初始序列（是否有序）有关；冒泡排序也有关。而简单选择排序中，所有趟数下来关键字总是总共比较n(n-1)/2次，每一趟关键字比较次数也是固定的。

Answer 2

冒泡排序有一种优化方法，就是在每趟冒泡的时候都检测这次是否有交换元素的顺序，如果没有交换就说明序列是排好序的，下次就不用再冒泡了！所以和初始序列是有关系的

Answer 3

折半插入排序中记录比较次数与初始序列无关。每躺排序寻找位置时，折半次数一定

Answer 4

选择排序无论它的初始顺序是怎样，它的比较次数都是n(n-1)/2.因为它是第一个数与后面的所有数进行比较，找出最值与第一个数进行互换，然后第二位数与后面所有数进行比较…因为它是数和其他数进行比较，比较期间不会判断数组的顺序，所以在程序结束前，它不会因为数组的顺序而停止。

Answer 5

冒泡排序会在每一趟排序的for 循环首句放置一个flag初始值为false;如果发生了交换，就让flag=true，如果一趟结束之后flag 没有变化，就说明表已经有序。排序结束。