最壞時(shí)間復(fù)雜度O（n^2）

希爾排序是插入排序的一種，是直接插入排序算法的一種更高效的改進(jìn)版。(學(xué)習(xí)希爾排序之前需要了解插入排序)。

插入排序是每次向右移動(dòng)一個(gè)步長(zhǎng)的距離，對(duì)當(dāng)前數(shù)值進(jìn)行操作。而希爾排序就是加大插入排序的步長(zhǎng)，這樣可以使得元素可以一次性的朝最終位置前進(jìn)一大步。

給出一個(gè)無序列表（下圖），假設(shè)希爾排序的gap（間隔/步長(zhǎng)）為4，可以得到四個(gè)子序列，下標(biāo)為0、4、8的序列1，下標(biāo)為1、5的序列2，下標(biāo)為2、6的序列3、下標(biāo)為3、7的序列4。

之后對(duì)每個(gè)子序列進(jìn)行插入排序

如對(duì)序列1進(jìn)行插入排序，將78與53比較，再將21先78做比較、再與53做比較，得到排序后的序列：21、53、78。

對(duì)所有子序列進(jìn)行插入排序后再重組得到下圖

之后將步長(zhǎng)縮小為2，重復(fù)上述操作，當(dāng)步長(zhǎng)為1時(shí)的操作結(jié)束后停止，就可以得到一個(gè)有序序列。

可能很多人剛開始接觸時(shí)，會(huì)覺得這樣會(huì)使插入算法變得更復(fù)雜，好像執(zhí)行的步驟增加了。不是這樣，雖然希爾排序的最壞時(shí)間復(fù)雜度與插入算法相同，但希爾排序的最優(yōu)時(shí)間復(fù)雜度是根據(jù)步長(zhǎng)序列的不同而不同的，最好的情況下，時(shí)間復(fù)雜度可以降到O（n^1.3）。

那這個(gè)步長(zhǎng)怎么取呢？這個(gè)難題至今沒有解答，但經(jīng)過大量的實(shí)驗(yàn)，人們還是積累了一定的經(jīng)驗(yàn)。

在希爾的原稿中建議的初始步長(zhǎng)是N/2，就是是將每一次排序分成兩半，雖然這樣取步長(zhǎng)在大多數(shù)情況下仍然比插入排序好，但也算不上較好，網(wǎng)上可以搜出很多取法，感興趣的可以搜來看看。這里我們就以希爾原稿中的步長(zhǎng)來講解。

灰線左邊是不需要移動(dòng)的值，右邊的值需要與左邊作比較，因此每次循環(huán)都需要將右邊的值與左邊作比較。操作順序：78、30、43、56、21。

78的下標(biāo)是4也就是步長(zhǎng)gap，那30的下標(biāo)是gap+1，43是gap+2，56是gap+3，21是gap+4。

還記得上文說的，希爾算法其實(shí)就是插入算法的改進(jìn)嘛，所以我們從插入算法入手。從內(nèi)往外，先寫每次需要執(zhí)行的比較代碼。

    1.先將一個(gè)子序列的灰線右邊與左邊做比較

    2.每個(gè)子序列執(zhí)行的操作相同，用一個(gè)循環(huán)控制不同序列的內(nèi)部比較

    3.此時(shí)一個(gè)步長(zhǎng)所要執(zhí)行的操作已結(jié)束，再用一個(gè)循環(huán)控制不同步長(zhǎng)的操作

主  編   |   張禎悅

責(zé)  編   |   馬原濤