????首先我們先來(lái)看一段希爾排序的c實(shí)現(xiàn)代碼：

????從這段代碼的邏輯來(lái)看僅僅需要三次相互嵌套的循環(huán)結(jié)構(gòu)（我們分別稱(chēng)為外層循環(huán)，中間循環(huán)，內(nèi)層循環(huán)）就可以實(shí)現(xiàn)希爾排序了，但只是簡(jiǎn)單的閱讀代碼我們并不能體會(huì)到各個(gè)位置上的元素在排序過(guò)程中都發(fā)生了哪些變化，從而我們無(wú)法很好的理解整個(gè)希爾排序進(jìn)行的過(guò)程，很可能導(dǎo)致我們理解的希爾排序與實(shí)際上真正的希爾排序之間出現(xiàn)偏差（掌握了錯(cuò)誤的排序方法）。

????為了能準(zhǔn)確理解希爾排序，我們需要用事實(shí)說(shuō)話(huà)。最直接的方法就是在上面的代碼中加入打印語(yǔ)句，這樣我們就可以在每次的排序行為發(fā)生之后馬上知道程序在這一步做了什么，交換了哪些元素。

????這里我們選擇對(duì){9,8,7,6,5,4,3,2,1,0}這個(gè)數(shù)組進(jìn)行升序排序，排序結(jié)果應(yīng)該是{0,1,2,3,4,5,6,7,8,9}。

????首先打印了這些元素排序之前的順序：

????在第一次進(jìn)入外層循環(huán)時(shí)gap=5，進(jìn)入內(nèi)層循環(huán)后第一次交換了下標(biāo)為0與下標(biāo)為5兩個(gè)位置上的元素（因?yàn)殚g隔gap是5，而且滿(mǎn)足內(nèi)層循環(huán)的判斷條件，0號(hào)位置上元素的值大于5號(hào)位置上元素的值），第二次交換了下標(biāo)為1與下標(biāo)為6位置上的元素，第三次交換了2與7位置上的元素，同理，第四交換了3與8，第五次交換了4與9。這時(shí)再進(jìn)入內(nèi)層循環(huán)時(shí)j>=0這個(gè)條件不滿(mǎn)足了，第一輪的內(nèi)層循環(huán)結(jié)束了。如下圖3所示：

????這時(shí)你可能要問(wèn)了，如果內(nèi)層循環(huán)中v[j]>v[j+gap]這個(gè)條件不滿(mǎn)足了增么辦呢？中間循環(huán)好像還沒(méi)有用到呀？每組相等間距的位置上的元素的順序排對(duì)了，可和其它組之間順序也是對(duì)的應(yīng)當(dāng)如何確保呢？不要著急，讓我們把間距再縮小一半，及當(dāng)gap=2時(shí)我們就會(huì)遇到使用中間循環(huán)的情況，體會(huì)這個(gè)過(guò)程將很好的解決上面的疑問(wèn)，并且能準(zhǔn)確理解希爾排序。讓我們開(kāi)始吧。

????當(dāng)gap=2時(shí)，基于上一步的排序結(jié)果，進(jìn)入內(nèi)層循環(huán)第一次交換了0位置與2位置上的元素，第二次交換了1與3位置上的元素，第三次交換了2與4位置上的元素，到目前位置原理都與上一步是相同的。但是第四次我們發(fā)現(xiàn)3與5位置上的元素不滿(mǎn)足v[j]>v[j+gap]這個(gè)條件了，于是內(nèi)層循環(huán)退出了。進(jìn)入中間循環(huán)之后又進(jìn)入了內(nèi)層循環(huán)（相當(dāng)于又開(kāi)始了去比較0與2,1與3,2與4位置上的元素這個(gè)過(guò)程了，這就檢查了之前錯(cuò)誤的組間順序關(guān)系，在這個(gè)例子中交換了上個(gè)結(jié)果第0個(gè)與第2個(gè)位置上的元素），在交換完0與2位置上的元素后，內(nèi)層循環(huán)交換1與3位置上的元素時(shí)又不滿(mǎn)足v[j]>v[j+gap]這個(gè)條件了，于是又進(jìn)入了中間循環(huán)，之后又進(jìn)入了內(nèi)層循環(huán)。每調(diào)出一次內(nèi)層循環(huán)中間循環(huán)i的值就加1，直到內(nèi)層循環(huán)中v[j]>v[j+gap]這個(gè)條件得到滿(mǎn)足（在這個(gè)例子中就是把內(nèi)循環(huán)1位置開(kāi)始比較變到了從5位置開(kāi)始比較），于是接下來(lái)第五次接著開(kāi)始比較5與7位置上元素的順序是否正確，接著第六次是6與8，第七次是7與9，第八次又發(fā)生了第四次出現(xiàn)的狀況，這時(shí)由于中間循環(huán)i值的變化已經(jīng)不需要檢查第5個(gè)元素之前組間元素是否正確了，所以第八次從第5個(gè)位置上的元素開(kāi)始檢查，交換了5與7位置上的元素，在之后進(jìn)入內(nèi)層循環(huán)都不滿(mǎn)足v[j]>v[j+gap]這個(gè)條件了。這個(gè)過(guò)程如下圖4所示：

????用文字描述圖4過(guò)程洋洋灑灑一大段，看起來(lái)也挺頭疼的。其實(shí)沒(méi)有必要咬文嚼字的理解，結(jié)合著圖1的程序和圖4的運(yùn)行結(jié)果稍微思考一下也是會(huì)很快理解這個(gè)排序過(guò)程的。簡(jiǎn)單來(lái)說(shuō)就是內(nèi)層循環(huán)條件滿(mǎn)足就進(jìn)行排序操作，內(nèi)層循環(huán)條件不滿(mǎn)足時(shí)就用中間循環(huán)檢查之前沒(méi)檢查過(guò)的排序結(jié)果是否正確，依靠?jī)?nèi)層循環(huán)把順序不對(duì)的調(diào)整過(guò)來(lái)（當(dāng)然是指相距gap的兩個(gè)元素），直到進(jìn)入下一個(gè)滿(mǎn)足條件的內(nèi)層循環(huán)繼續(xù)進(jìn)行排序操作（這時(shí)之前的元素都是被檢查過(guò)的）。

????最后我們把gap的值減小為1進(jìn)行最后一次排序，這時(shí)我們發(fā)現(xiàn)進(jìn)入內(nèi)層循環(huán)時(shí)v[j]>v[j+gap]這個(gè)條件每次都不滿(mǎn)足，因此沒(méi)有元素被交換。如下圖5所示：

????

????最后打印出最終的排序結(jié)果如下圖6所示：

????好了，整個(gè)希爾排序的過(guò)程已經(jīng)全部介紹完了。最后介紹一下希爾排序是什么，希爾排序是插入排序的一種，但其中需要用到一個(gè)縮小量來(lái)不斷約束之前這個(gè)縮小量取較大值時(shí)排序結(jié)果的毛糙感（大體上看著有個(gè)順序，但又有些錯(cuò)誤的排序穿插其中）。

程序代碼：