在上一篇博客中，介紹了插入排序的第一種化戳，直接插入排序。再加上前面介紹過的快速排序扫尖，冒泡排序和簡單選擇排序掠廓。這四種排序可以不太嚴謹?shù)亩x為八種排序算法中的較簡單的排序算法，接下來就要介紹的就是比較復雜的排序算法却盘，所謂的復雜其實指的就是算法的思想上黄橘，實現(xiàn)的邏輯上要復雜一些。但是萬變不離其宗塞关，大量的代碼也許換來的僅僅是很小的效率的提升，但是千里之堤毀于蟻穴小压，往往是這些小小的細節(jié)會趕走大量的用戶椰于，這個損失是不可估量的。又說跑題了蜻牢，回到正題繼續(xù)介紹今天的主角：希爾排序偏陪。
可能大家在看到之前幾個排序算法的時候，通過它名字就可以比較形象的猜出這個排序算法的主要特征抱虐，甚至是核心的思想饥脑。但是今天要介紹的是八大排序算法中唯一一個以發(fā)明者的名字命名的排序算法懦冰。在物理學轩娶，數(shù)學中，以科學家名字命名的公式，定義真的是數(shù)不勝數(shù)椰弊，就牛頓牛老師的名字在我學過的知識中就出現(xiàn)了五六次，力的單位牛頓贤重；牛頓一二三定律清焕；牛頓萊布尼茨方程等等。但是可能大家可能沒有注意滚停，在計算機領(lǐng)域中粥惧，以大師的人名命名的算法包括發(fā)明真的是少之又少∑鹛瑁“約翰·阿塔那索夫”這個人名可能很多人甚至是同行們都很陌生咏删，簡單的介紹一下，這個人是第一個發(fā)明現(xiàn)代電子計算機的人督函，也被成為“電子計算機之父”侨核。我覺得約翰·阿塔那索夫教授所做出的貢獻絕對應(yīng)該和愛迪生，牛頓搓译，瓦特等大師一樣被人們牢記些己，但是甚至對他的名字大家都知之甚少嘿般。直到前幾年涯冠，模仿游戲那部電影上映才讓大家認識了“計算機之父”圖靈的故事，我覺得這個現(xiàn)象真的很讓我困惑蛇更。也許甚至是那樣偉大的科學家靈魂里也都或多或少具有著一個程序員低調(diào)不善言辭的性格吧派任。
希爾排序，是由Donald Shell于1959年提出的掌逛。它作為插入排序的一種豆混，對直接插入排序進行了很大的優(yōu)化，由于直接插入排序在每次和之前的元素進行比較的時候如果符合條件就要進行插入操作皿伺，這樣做，如果這樣會造成較遠的元素需要很多次的無用交換才能放到正確的位置屈暗，這樣的效率是很低的脂男。 希爾排序會首先比較較遠的元素，這樣可以使離正確位置很遠的元素很快的回到合適的位置弃甥≈希可能有人會問，這不是多此一舉嗎瓶珊，正常執(zhí)行直接插入排序就好了耸彪，還多整一步。關(guān)于這個疑惑唱较，我舉一個簡單例子，大家應(yīng)該就能理解這一步的巧妙之處了南缓。新生報到的時候大家互相不認識汉形，排成一列站隊的時候也是高矮胖瘦，參差不齊获雕。這個時候的隊列就很像待排序的數(shù)組届案。這個時候老師來了罢艾，小個在前大個在后排隊，這個時候童漩，比如說隊尾站的恰巧是個字很小的同學春锋，如果按直接插入排序的思想的邏輯，老師會從前到后期奔，依次進行排序呐萌，當遍歷到隊尾的時候才會對他進行排序，如果隊伍20個人肺孤，他就要移動二十次赠堵。但是在正常情況下，老師如果發(fā)現(xiàn)隊尾有一個或幾個小個子茫叭，會馬上把他們叫到前面杂靶，把排頭幾個大個子調(diào)到隊尾酱鸭，這就是希爾排序的巧妙之處垛吗。接下來就是這個算法的詳細介紹和實現(xiàn)。
首先蔚舀，這個算法引入了一個新的概念锨络，叫做步長。在希爾排序中需要把整個元素分成N組礼患，而這個步長決定著具體分幾組掠归，也就是說，哪個元素和距離他長度+步長的元素為一組肤粱。舉個例子厨相，一個數(shù)組：[5,4,3,2,1]，如果步長為3庶骄，五個元素步長為3绪撵，首先[5,2]一組，[4,1]一組幻碱，[3]一組细溅。而分組之后組內(nèi)進行直接插入排序。組內(nèi)的元素變?yōu)?[2,5],[1,4],[3]恍风。然很關(guān)鍵，將元素復位凯楔，[2,1,3,5,4]锦募。然后把步長設(shè)為2，[2,3,4]一組虐骑，[1,5]一組赎线。最后，將步長設(shè)為1的時候颠黎，就是我們熟悉的直接插入排序了滞项，前面的步驟的目的就是將較遠的元素通過盡可能少的步驟移動到正確的位置，在最后步長為一的時候執(zhí)行一次直接插入操作，這時的數(shù)組基本上只需要移動很少的次數(shù)就能實現(xiàn)最終的排序律杠。這就是希爾排序的全部過程竞惋，在執(zhí)行直接插入排序之前，對整個數(shù)組進行優(yōu)化嗓奢。接下來進行代碼實現(xiàn)浑厚。
1、設(shè)置步長
var step = 1;
var l = arr.length;
while(step<l/3){h=h*3;}
希爾排序和直接插入排序的區(qū)別就是引入了步長的概念物蝙，步長如何選擇就變得很關(guān)鍵了敢艰，關(guān)于取步長的算法就完全可以長篇大論的討論很久。這里就不贅述了震嫉，鑒于較小的數(shù)據(jù)量，這里我取步長為：3,1扼睬。如果數(shù)據(jù)量很大换衬，可以將步長設(shè)為5，3担映， 1或者7, 5叫潦， 3， 1.這里關(guān)于步長的取法就不多說了短蜕。
while(step>=1){
for(var i = step;i < l;i++){
for(var j = i;j >= step && arr[j-step] > arr[j];j = j-step){
var temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
step = Math.floor(step/3);
}
上面這10行代碼其實就是希爾排序的核心實現(xiàn)朋魔，可能有的人會覺得似曾相識卿操，和直接插入排序有點像啊。沒錯扇雕，當步長step為1的時候窥摄，執(zhí)行的就是直接插入排序。步長大于1的時候?qū)Ξ斍霸睾途嚯x加上步長的元素進行比較哨苛，如果前面的元素大于后面的元素莹菱，那么執(zhí)行交換操作。然后步長減小迹缀，直到步長為1，執(zhí)行直接插入操作票摇。
這就是希爾排序的全部介紹矢门。感謝閱讀灰蛙。
