希爾排序又稱“縮小增量排序”，是插入排序的一種。直接插人排序，當(dāng)待排序的記錄個(gè)數(shù)較少且待排序序列的關(guān)鍵字基本有序時(shí)，效率較高。希爾排序基于以上兩點(diǎn)，從“減少記錄個(gè)數(shù)”和“序列基本有序”兩個(gè)方面對(duì)直接插入排序進(jìn)行了改進(jìn)。

（1）步驟：

1. 先選定一個(gè)小于N的整數(shù)gap作為第一增量，然后將所有距離為gap的元素分在同一組，并對(duì)每一組的元素進(jìn)行直接插入排序。然后再取一個(gè)比第一增量小的整數(shù)作為第二增量，重復(fù)上述操作…

2. 當(dāng)增量的大小減到1時(shí)，就相當(dāng)于整個(gè)序列被分到一組，進(jìn)行一次直接插入排序，排序完成。

（2）特點(diǎn)：

1. 縮小增量

2. 多遍插入排序

3. 時(shí)間復(fù)雜度：O(n 1.3 n^{1.3}n 1.3 )

4. 空間復(fù)雜度：O(1)

5. 穩(wěn)定性：不穩(wěn)定

（3）動(dòng)圖演示：

這里重要的是理解分組思想，每一個(gè)組其實(shí)就是一個(gè)插入排序，相當(dāng)于進(jìn)行多次插入排序。

（4）C語(yǔ)言代碼實(shí)現(xiàn)如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int shell_sort(int arr[],int n)
{
    register int i, j, tmp;
    int step;

    for(step = n/2; step > 0;step /= 2)/*增量步長(zhǎng)*/
    {
        /*step = 4 2 1*/
        for(i = step; i < n; i++)
        {
            tmp = arr[i];
            j = i - step;
            for(;j >= 0 && tmp < arr[j];)
            {
                arr[j + step] = arr[j];
                j -= step;
            }
            arr[j + step] = tmp;

        }
    }
}

#define LENGTH 8

int main( int argc, int *argv[])
{
    int i;
    int arr[LENGTH] = {6,5,3,1,8,7,2,4};

    for(i=0;i<LENGTH;i++)
    printf("%d ",arr[i]);printf("\n");

    shell_sort(arr,LENGTH);

    for(i = 0;i < LENGTH;i++)
    printf("%d ", arr[i]);printf("\n");
}

如果我們編譯并運(yùn)行上述程序，那么它應(yīng)該產(chǎn)生以下結(jié)果：

6 5 3 1 8 7 2 4 
1 2 3 4 5 6 7 8