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