算法引入

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

插入排序法有2個(gè)特點(diǎn)：

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

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

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

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

h-sort

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

答案：

原序列有5個(gè)間隔為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個(gè)子序列都排好序，那么原來(lái)都序列就變成了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】

想一想：

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

再想一想：

希爾排序

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

問(wèn)題1： 為什么只要最終步長(zhǎng)為 1 任何步長(zhǎng)串行都可以完成排序？

問(wèn)題2:   既然如此，為什么開(kāi)始不直接使用插入排序？ 而要計(jì)算n-sorts?

算法實(shí)現(xiàn)

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

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

算法復(fù)雜度

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