????希爾排序是插入排序的一種，又稱“縮小增量排序”，希爾排序是直接插入排序算法的一種更高效的改進(jìn)版本，排序相關(guān)文章推薦:C語(yǔ)言中的排序算法。

希爾排序的基本思想

????設(shè)等待排序等元素序列有n個(gè)元素，首先取一個(gè)整數(shù)increment（小于n）作為間隔將全部元素分為n/increment個(gè)子序列，所有距離為increment的元素放在同一個(gè)子序列中，在每一個(gè)子序列中分別實(shí)行直接插入排序，然后縮小間隔increment，重復(fù)上述子序列劃分和排序工作，直到最后取increment=1，將所有元素放在同一個(gè)子序列中排序?yàn)橹梗摲椒▽?shí)質(zhì)上是一種分組插入方法.

關(guān)于增量（increment）的取值

????希爾排序的復(fù)雜度和增量序列是相關(guān)的，一般的初次取序列長(zhǎng)度的一半為增量，以后每次減半，直到增量為1，希爾排序中對(duì)于增量序列的選擇十分重要，直接影響到希爾排序的性能，一些經(jīng)過(guò)優(yōu)化的增量序列如Hibbard經(jīng)過(guò)復(fù)雜證明可使得最壞時(shí)間復(fù)雜度為O(n3/2)?。

????{1,2,4,8,...}這種序列并不是很好的增量序列，使用這個(gè)增量序列的時(shí)間復(fù)雜度（最壞情形）是O(n^2)。

??? Hibbard提出了另一個(gè)增量序列{1,3,7，...,2^k-1}，這種序列的時(shí)間復(fù)雜度(最壞情形)為O(n^1.5)。

??? Sedgewick提出了幾種增量序列，其最壞情形運(yùn)行時(shí)間為O（n^1.3）,其中最好的一個(gè)序列是{1,5,19,41,109,...}。?

代碼實(shí)現(xiàn)

?

/* 希爾排序*/int num[5] = {3, 7, 1, 8, 5};int cur;int i, j;int length = sizeof(num)/sizeof(num[0]);????int?incre;????incre?=?length?/?2;while (incre >= 1)    {for (i = incre; i < length; i++)        {            cur = num[i];    //待排序元素for (j = i - incre; j >= 0 && num[j] > cur; j = j - incre)            {                num[j + incre] = num[j];    //元素向后移動(dòng)            }            num[j + incre] = cur;    //插入待排序元素        }        incre = incre / 2;    //增量減半    }

?

??? while里面的代碼其實(shí)和插入排序的代碼沒(méi)多大區(qū)別，就是在兩個(gè)for循環(huán)外面套了一個(gè)while再修改了一下內(nèi)部的for循環(huán)，可以對(duì)照看一下下面列出來(lái)的插入排序的for循環(huán)。

?

for (i = 1; i < length; i++)    {        cur = num[i];    //待排序元素for (j = i - 1; j >= 0 && num[j] > cur; j--)        {            num[j + 1] = num[j];        }        num[j + 1] = cur;    }

?

排序過(guò)程

????以5，7，8，3，1，2，4，6為例。

????下面有顏色的是邏輯上的分組，并沒(méi)有實(shí)際地進(jìn)行分組操作，在數(shù)組中的位置還是原來(lái)的樣子，只是將它們看成這么幾個(gè)分組（邏輯上分組）。

????每個(gè)分組進(jìn)行插入排序后，各個(gè)分組就變成了有序的了（整體不一定有序）。

????此時(shí)，整個(gè)數(shù)組變的部分有序了（有序程度可能不是很高）。

????然后縮小增量為上個(gè)增量的一半:2，繼續(xù)劃分分組，此時(shí)，每個(gè)分組元素個(gè)數(shù)多了，但是，數(shù)組變的部分有序了，插入排序效率同樣不高。

????同理對(duì)每個(gè)分組進(jìn)行排序（插入排序），使其每個(gè)分組各自有序。

????最后設(shè)置增量為上一個(gè)增量的一半：1，則整個(gè)數(shù)組被分為一組，此時(shí)，整個(gè)數(shù)組已經(jīng)接近有序了，插入排序效率高。

????同理，對(duì)這僅有的一組數(shù)據(jù)進(jìn)行排序，排序完成。