算法引入

希爾排序（Shell Sort）是Shell提出來的，對插入排序法的改進，也是最早突破復(fù)雜度O(n2)的排序算法。

插入排序法有2個特點：

1.  插入排序在對幾乎已經(jīng)排序的數(shù)據(jù)操作時，效率高，可以達到線性時間

2.  插入排序一般來說是低效的，其每次只能將數(shù)據(jù)移動一位：

   假設(shè)一個極端的例子，如果最小的數(shù)據(jù)在一個已按升序排好序的數(shù)組的末端。冒泡排序或插入排序可能會進行 n 次的比較和交換才能將該數(shù)據(jù)移至正確位置。

希爾排序提供了一個辦法，可以直接比較交換間隔較遠(yuǎn)的數(shù)據(jù)

h-sort

希爾排序的關(guān)鍵思想是先用間隔較遠(yuǎn)的數(shù)據(jù)相互排序，這樣有機會把位置很偏的數(shù)據(jù)迅速安放到正確的位置。首先我們介紹一個新概念：h-sort

答案：

原序列有5個間隔為5的子序列：

（a1,a6,a11）->【62，17，25】，

（a2,a7,a12）->【83，95，28】，

（a3,a8）->【18，86】，

（a4,a9）->【53，47】，

（a5,a10）->【07，69】

如果上述5個子序列都排好序，那么原來都序列就變成了5-sorted.

（a1,a6,a11）->【62，17，25】->  （a1,a6,a11）->【17，25，62】

（a2,a7,a12）->【83，95，28】->   (a2,a7,a12）->【28，83，95】

（a3,a8）->【18，86】->                （a3,a8）->【18，86】

（a4,a9）->【53，47】->                （a4,a9）->【47，53】

（a5,a10）->【07，69】->                 (a5,a10）->【07，69】

想一想：

如果一個序列是h-sorted,  那么這個序列是已經(jīng)排好序的了.這句話對不對？

再想一想：

希爾排序

 我們定義一個從大到小的數(shù)列叫做步長序列， 只要最終步長為 1 任何步長串行都可以使用。希爾排序就是用步長序列定義的步長對數(shù)組用插入排序法反復(fù)排序?qū)^程。

問題1： 為什么只要最終步長為 1 任何步長串行都可以完成排序？

問題2:   既然如此，為什么開始不直接使用插入排序？ 而要計算n-sorts?

算法實現(xiàn)

為什么循環(huán)從i=gap開始？， 因為我們對所以子序列用插入排序法進行排序；而在插入排序法中，第一個元素可以看做已經(jīng)排好序的，這里有g(shù)ap個子序列，所以前面一共有g(shù)ap個排好序的元素。

學(xué)而時嘻之,不亦樂乎～， 來做個填充練習(xí)：

算法復(fù)雜度

希爾排序是按照不同步長對元素進行插入排序，當(dāng)剛開始元素很無序的時候，步長最大，所以插入排序的元素個數(shù)很少，速度很快；當(dāng)元素基本有序了，步長很小，插入排序?qū)τ谟行虻男蛄行屎芨?。所以，希爾排序的時間復(fù)雜度會比o(n^2)好一些。