前言

希爾排序是Donald Shell于1959年提出來(lái)的一種排序算法，它是第一批突破O(n²)這個(gè)時(shí)間復(fù)雜度的算法之一。大話(huà)數(shù)據(jù)結(jié)構(gòu)對(duì)這個(gè)算法的講解，我看得一知半解的，之后網(wǎng)上找了下資料，發(fā)現(xiàn)維基百科對(duì)這個(gè)算法的講解非常不錯(cuò)，特在此整理一波。

原理

希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：

• 插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線(xiàn)性排序的效率
• 但插入排序一般來(lái)說(shuō)是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位

image

什么鬼.png

說(shuō)說(shuō)我的個(gè)人理解：

希爾排序其實(shí)就是直接插入排序的升級(jí)，原理就是先將整個(gè)待排序列按照某個(gè)增量（也稱(chēng)步長(zhǎng)）分割成若干個(gè)子序列分別進(jìn)行直接插入排序，然后合并，之后依次縮小增量大小在進(jìn)行排序，當(dāng)增量足夠?。ㄍǔ?）時(shí)，再對(duì)全體元素進(jìn)行直接插入排序，而此時(shí)需排序的數(shù)據(jù)幾乎是已排好的了，所以此時(shí)插入排序較快。

當(dāng)然如果你覺(jué)得文字比較乏味就看下面的這些例子吧

例如，假設(shè)有這樣一組數(shù)[9 1 5 8 3 7 4 6 2]，如果我們先以步長(zhǎng)為4進(jìn)行分割，就是這樣：

9 1 5 8
3 7 4 6 
2

然后我們對(duì)每列進(jìn)行排序（注意每列哦）：

2 1 4 6
3 7 5 8
9

將上述四行數(shù)字，依序合并我們得到：[ 2 1 4 6 3 7 5 8 9 ]。此時(shí)2已經(jīng)往前移，而8、9已經(jīng)在后兩位，然后再以2為步長(zhǎng)進(jìn)行分割：

2 1
4 6
3 7
5 8
9

繼續(xù)排序：

2 1
3 6
4 7
5 8
9

合并得到［ 2 1 3 6 4 7 5 8 9］，此時(shí)序列已經(jīng)基本有序，需交換數(shù)據(jù)的情況大為減少，這時(shí)整列進(jìn)行直接插入排序效率就非常高。

最終完成排序過(guò)程，也就是步長(zhǎng)為1時(shí)，得到最終序列為：1 2 3 4 5 6 7 8 9。

笑.png

示例代碼（C）

#include <stdio.h>
#define MAXSIZE 100 //用于要排序數(shù)組的最大值 

typedef struct      //定義一個(gè)順序表結(jié)構(gòu) 
{
    int r[MAXSIZE+1];   //用于存儲(chǔ)要排序數(shù)組，r[0]用作哨兵或者臨時(shí)變量 
    int length;         //用于存儲(chǔ)順序表的最大長(zhǎng)度 
}SqList;

void ShellSort(SqList *L)
{
    int i,j;
    int gap=L->length;  //獲取數(shù)組長(zhǎng)度 
    
    for(gap/=2;gap>=1;gap/=2)   //步長(zhǎng) 
        for(i=gap+1; i<=L->length; i++) //從第gap+1個(gè)元素開(kāi)始，因?yàn)閞[0]被當(dāng)做臨時(shí)變量 
            if(L->r[i] < L->r[i-gap])   //每個(gè)元素與自己組內(nèi)的數(shù)據(jù)進(jìn)行直接插入排序 
            {
                L->r[0]=L->r[i];    //把要交換的數(shù)據(jù)暫存的L->r[0]中 
                for(j=i-gap; j>0&&L->r[j] > L->r[0]; j-=gap)    
                    L->r[j+gap] = L->r[j];  //記錄后移，查找插入位置 
                    
                L->r[j+gap]=L->r[0];    //插入 
            }
} 

int main()
{
    int i=0;
    int array[] = {39,80,76,41,13,29,50,78,30,11,100,7,41,86};
    
    SqList L;
    L.length = sizeof(array)/sizeof(array[0]);  //獲取數(shù)組長(zhǎng)度 
    for(i=0;i<L.length;i++)
    {
        L.r[i+1]=array[i];  //把數(shù)組存入順序表結(jié)構(gòu) 
    }
    ShellSort(&L);
    
    //輸出排序后的數(shù)組 
    for(i=0;i<L.length;i++) 
    {
        printf("%d ",L.r[i+1]);
    }
    return 0;
}

可能有幾個(gè)步驟略難懂，這里解釋下：

• 第17行：這里的步長(zhǎng)采用,最終判斷條件為gap>=1,這里不管你數(shù)組初始長(zhǎng)度為多少，除到最后均會(huì)等于1，而等于1時(shí)，就是執(zhí)行最后一次循環(huán)，這個(gè)時(shí)候也就是所有元素進(jìn)行直接插入排序。當(dāng)然也可寫(xiě)成gap>0。

• 第18行：在前面定義順序表結(jié)構(gòu)時(shí)，我們加多了一位，也就是把r[0]當(dāng)做交換數(shù)據(jù)時(shí)的臨時(shí)變量。

• 第22~23行：對(duì)于這個(gè)循環(huán)我們直接拿上面的例子中的一列進(jìn)行講解（9 3 2）：

image

當(dāng)時(shí)，9和3進(jìn)行了一次交換，變?yōu)?code>（3 9 2）(位置為1 5 9），之后在時(shí)，做出的交換如上圖所示（圖略差...)，分為三個(gè)步驟：

• 第一次進(jìn)入循環(huán)，執(zhí)行23行得，此時(shí)該列數(shù)值變?yōu)?code>(3 9 9)；
• 繼續(xù)第二次循環(huán)，同樣執(zhí)行循環(huán)，此時(shí)變?yōu)?code>（3 3 9）；
• 跳出循環(huán)(注意：跳出循環(huán)時(shí)多執(zhí)行了一次)，執(zhí)行，最終變?yōu)?code>(2 3 9)。

步長(zhǎng)（增量）選擇

步長(zhǎng)的選取非常關(guān)鍵，但是步長(zhǎng)的選擇沒(méi)有統(tǒng)一規(guī)定，也沒(méi)絕對(duì)的規(guī)律。只要滿(mǎn)足最后一個(gè)步長(zhǎng)為1即可。Donald Shell最初建議步長(zhǎng)選擇為,雖然這樣去可以比類(lèi)的算法更好，但仍然有減少平均時(shí)間和最差時(shí)間的余地。維基百科給出的部分步長(zhǎng)與最壞情況下復(fù)雜度有：

image

已知的最好步長(zhǎng)序列是由Sedgewick提出的(1, 5, 19, 41, 109,...)，該序列的項(xiàng)來(lái)自和這兩個(gè)算式。這項(xiàng)研究也表明“比較在希爾排序中是最主要的操作，而不是交換?！庇眠@樣步長(zhǎng)序列的希爾排序比插入排序要快，甚至在小數(shù)組中比快速排序和堆排序（后續(xù)博客整理），但是在涉及大量數(shù)據(jù)時(shí)希爾排序還是比快速排序慢。