希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序，希爾排序法又稱縮小增量法。查看完整代碼

1、算法思想：通過某個(gè)增量將數(shù)組元素劃分為若干組，然后分組進(jìn)行插入排序，隨后逐步縮小增量，繼續(xù)按組進(jìn)行插入排序操作，直至增量為1。在希爾排序中，增量序列g(shù)ap的取法必須滿足：最后一個(gè)步長必須是 1。各組內(nèi)的排序通常采用直接插入法。由于開始時(shí)i的取值較大，每組內(nèi)記錄數(shù)較少，所以排序比較快。隨著不斷增大，每組內(nèi)的記錄數(shù)逐步增多，但由于已經(jīng)按排好序，因此排序速度也比較快

2、算法步驟：(1)、確定增量gas的大小，建議步長選擇為N/2并且對(duì)步長取半直到步長達(dá)到1，此時(shí)會(huì)把待排序數(shù)列分成若干組

(2)、對(duì)每個(gè)組進(jìn)行直接插入排序，重復(fù)(1) (2)操作，當(dāng)步長的值減小到 1 時(shí)，整個(gè)數(shù)據(jù)合成為一組，構(gòu)成一組有序記錄，則完成排序。

3、圖解：

初始時(shí)，6個(gè)元素?cái)?shù)組，在第一趟排序中，我們不妨設(shè) gap1 = N / 2 = 3，即相隔距離為 3 的元素組成一組，可以分為 3組。接下來，按照直接插入排序的方法對(duì)每個(gè)組進(jìn)行排序。

在第二趟排序中，再次把 gap 縮小一半，即gap2= gap / 2 = 1。 這樣相隔距離為 1 的元素組成一組，即只有一組。按照直接插入排序的方法對(duì)每個(gè)組進(jìn)行排序。此時(shí)，排序已經(jīng)結(jié)束。

4.算法分析：

時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度為O(NlogN)。

空間復(fù)雜度：空間復(fù)雜度顯然為O(1)，僅僅需要一個(gè)交換變量。

穩(wěn)定性：是一種不穩(wěn)定的排序算法。