希尔排序面试题

001什么是希尔排序？

1)希尔排序又称递减增量排序算法，是插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。希尔排序目的为了加快速度改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。在此我们选择增量 gap=length/2，缩小增量以 gap = gap/2 的方式，用序列 {n/2,(n/2)/2...1} 来表示。

2) 算法图解

【1】下面数组的长度length为8，初始增量第一趟 gap = length/2 = 4，即让第1个数和第5个数比较，第2个数和第6个数进行比较，第3个数和第7个数进行比较，第4个数和第8个数进行比较，最终结果是【1 5 2 3 7 6 9 4】

【2】第二趟，gap=gap/2=2,增量缩小为 2。即让第1个数、第3个数、第5个数和第7个数进行比较，第2个数、第4个数、第6个数和第8个数进行比较，最终结果是【1 3 2 4 7 5 9 6】

【3】第三趟，gap=gap/2=1,增量缩小为 1。所有的数进行比较得到的结果【1 2 3 4 5 6 7 9】

002希尔排序的代码实现？

public static void shellSort(int[] args) {
    for (int gap = args.length / 2; gap > 0; gap /= 2) {
        // 从第gap个元素，逐个对其所在组进行直接插入排序操作
        for (int i = gap; i < args.length; i++) {
            int j = i;
            int temp = args[j];
            if (args[j] < args[j - gap]) {
                while (j - gap >= 0 && temp < args[j - gap]) {
                    // 移动法
                    args[j] = args[j - gap];
                    j -= gap;
                }
                args[j] = temp;
            }
        }    
    }
}    

003希尔排序的组内排序采用的是( )。

A. 直接插入排序
B. 折半插入排序
C. 快速排序
D. 归并排序
答案: A  
解析: 希尔排序的思想是：先将待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成），分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

004设 一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为( )。

A.  40，50，20，95
B.  15，40，60，20
C.  15，20，40，45
D.  45，40，15，20
答案: B
解析：希尔排序属于插入类排序，是将整个有序序列分割成若干小的子序列分别进行插入排序。排序过程是先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di = 1，即所有记录放进一个组中排序为止。
题目中：d = 4，排序之后为：15,40,60,20,50,70,95,45
              d = 2，排序之后为：15,20,50,40,60,45,95,70
              d = 3，排序之后为：15,20,40,45,50,60,70,95