詳細(xì)代碼請(qǐng)參考Algorithm。參考代碼比文字好理解萄唇。
希爾排序，也稱(chēng)遞減增量排序算法术幔，是插入排序的一種高速而穩(wěn)定的改進(jìn)版本另萤。因Donald Shell于1959年提出而得名。希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)诅挑， 效率高四敞， 即可以達(dá)到線(xiàn)性排序的效率；但插入排序一般來(lái)說(shuō)是低效的拔妥， 因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位忿危。該方法的基本思想是：先將整個(gè)待排元素序列分割成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成的）分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排序没龙，待整個(gè)序列中的元素基本有序（增量足夠衅坛）時(shí)，再對(duì)全體元素進(jìn)行一次直接插入排序硬纤。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下（接近最好情況）解滓，效率是很高的，因此希爾排序在時(shí)間效率上有較大提高筝家。
希爾排序總結(jié)來(lái)說(shuō)就是把記錄按步長(zhǎng) gap 分組洼裤，對(duì)每組記錄采用直接插入排序方法進(jìn)行排序。隨著步長(zhǎng)逐漸減小溪王，所分成的組包含的記錄越來(lái)越多逸邦，當(dāng)步長(zhǎng)的值減小到 1 時(shí)，整個(gè)數(shù)據(jù)合成為一組在扰，構(gòu)成一組有序記錄缕减，則完成排序。
算法分解
初始時(shí)芒珠，有一個(gè)大小為 10 的無(wú)序序列桥狡。在第一趟排序中，我們不妨設(shè) gap1 = N / 2 = 5皱卓，即相隔距離為 5 的元素組成一組裹芝，可以分為 5 組。接下來(lái)娜汁，按照直接插入排序的方法對(duì)每個(gè)組進(jìn)行排序嫂易。
在第二趟排序中，我們把上次的 gap 縮小一半掐禁，即 gap2 = gap1 / 2 = 2 (取整數(shù))怜械。這樣每相隔距離為 2 的元素組成一組颅和，可以分為 2 組。按照直接插入排序的方法對(duì)每個(gè)組進(jìn)行排序缕允。
在第三趟排序中峡扩，再次把 gap 縮小一半，即gap3 = gap2 / 2 = 1障本。 這樣相隔距離為 1 的元素組成一組教届，即只有一組。按照直接插入排序的方法對(duì)每個(gè)組進(jìn)行排序驾霜。此時(shí)案训，排序已經(jīng)結(jié)束。
需要注意一下的是粪糙，圖中有兩個(gè)相等數(shù)值的元素 5 和 5 强霎。我們可以清楚的看到，在排序過(guò)程中猜旬，兩個(gè)元素位置交換了。所以倦卖，希爾排序是不穩(wěn)定的算法洒擦。
算法分析
步長(zhǎng)的選擇是希爾排序的重要部分。只要最終步長(zhǎng)為1任何步長(zhǎng)序列都可以工作怕膛。算法最開(kāi)始以一定的步長(zhǎng)進(jìn)行排序熟嫩。然后會(huì)繼續(xù)以一定步長(zhǎng)進(jìn)行排序，最終算法以步長(zhǎng)為1進(jìn)行排序褐捻。當(dāng)步長(zhǎng)為1時(shí)掸茅，算法變?yōu)椴迦肱判颍@就保證了數(shù)據(jù)一定會(huì)被排序柠逞。
Donald Shell 最初建議步長(zhǎng)選擇為N/2并且對(duì)步長(zhǎng)取半直到步長(zhǎng)達(dá)到1昧狮。雖然這樣取可以比O(N2)類(lèi)的算法（插入排序）更好，但這樣仍然有減少平均時(shí)間和最差時(shí)間的余地板壮《好可能希爾排序最重要的地方在于當(dāng)用較小步長(zhǎng)排序后，以前用的較大步長(zhǎng)仍然是有序的绰精。比如撒璧，如果一個(gè)數(shù)列以步長(zhǎng)5進(jìn)行了排序然后再以步長(zhǎng)3進(jìn)行排序，那么該數(shù)列不僅是以步長(zhǎng)3有序笨使，而且是以步長(zhǎng)5有序卿樱。如果不是這樣，那么算法在迭代過(guò)程中會(huì)打亂以前的順序硫椰，那就不會(huì)以如此短的時(shí)間完成排序了繁调。
直接插入排序和希爾排序的比較
直接插入排序是穩(wěn)定的萨蚕；而希爾排序是不穩(wěn)定的。直接插入排序更適合于原始記錄基本有序的集合涉馁。希爾排序的比較次數(shù)和移動(dòng)次數(shù)都要比直接插入排序少门岔，當(dāng)N越大時(shí)，效果越明顯烤送。 在希爾排序中寒随，增量序列g(shù)ap的取法必須滿(mǎn)足：最后一個(gè)步長(zhǎng)必須是 1 。 直接插入排序也適用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)帮坚；希爾排序不適用于鏈?zhǔn)浇Y(jié)構(gòu)妻往。
