001什么是希爾排序？

1)希爾排序又稱遞減增量排序算法，是插入排序的改進(jìn)版。它與插入排序的不同之處在于，它會優(yōu)先比較距離較遠(yuǎn)的元素。希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個序列中的記錄"基本有序"時，再對全體記錄進(jìn)行依次直接插入排序。希爾排序目的為了加快速度改進(jìn)了插入排序，交換不相鄰的元素對數(shù)組的局部進(jìn)行排序，并最終用插入排序?qū)⒕植坑行虻臄?shù)組排序。在此我們選擇增量 gap=length/2，縮小增量以 gap = gap/2 的方式，用序列 {n/2,(n/2)/2...1} 來表示。

2) 算法圖解

【1】下面數(shù)組的長度length為8，初始增量第一趟 gap = length/2 = 4，即讓第1個數(shù)和第5個數(shù)比較，第2個數(shù)和第6個數(shù)進(jìn)行比較，第3個數(shù)和第7個數(shù)進(jìn)行比較，第4個數(shù)和第8個數(shù)進(jìn)行比較，最終結(jié)果是【1 5 2 3 7 6 9 4】

【2】第二趟，gap=gap/2=2,增量縮小為 2。即讓第1個數(shù)、第3個數(shù)、第5個數(shù)和第7個數(shù)進(jìn)行比較，第2個數(shù)、第4個數(shù)、第6個數(shù)和第8個數(shù)進(jìn)行比較，最終結(jié)果是【1 3 2 4 7 5 9 6】

【3】第三趟，gap=gap/2=1,增量縮小為 1。所有的數(shù)進(jìn)行比較得到的結(jié)果【1 2 3 4 5 6 7 9】

002希爾排序的代碼實(shí)現(xiàn)？

public static void shellSort(int[] args) {
    for (int gap = args.length / 2; gap > 0; gap /= 2) {
        // 從第gap個元素，逐個對其所在組進(jìn)行直接插入排序操作
        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希爾排序的組內(nèi)排序采用的是( )。

A. 直接插入排序
B. 折半插入排序
C. 快速排序
D. 歸并排序
答案: A  
解析: 希爾排序的思想是：先將待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成），分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進(jìn)行一次直接插入排序。

004設(shè) 一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為( )。

A.  40，50，20，95
B.  15，40，60，20
C.  15，20，40，45
D.  45，40，15，20
答案: B
解析：希爾排序?qū)儆诓迦腩惻判颍菍⒄麄€有序序列分割成若干小的子序列分別進(jìn)行插入排序。排序過程是先取一個正整數(shù)d1<n，把所有序號相隔d1的數(shù)組元素放一組，組內(nèi)進(jìn)行直接插入排序；然后取d2<d1，重復(fù)上述分組和排序操作；直至di = 1，即所有記錄放進(jìn)一個組中排序?yàn)橹埂?br /> 題目中：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