Question

对于一个数组进行排序，排序次数和数组初始状态无关的是 归并排序 快速排序 堆排序 插入排序？

对于一个数组进行排序，排序次数和数组初始状态无关的是
归并排序
快速排序
堆排序
插入排序

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次

可见归并排序的比较次数就不固定，随着初始状态不同而不同。