在上一篇博客中，介紹了插入排序的第一種，直接插入排序渣刷。再加上前面介紹過(guò)的快速排序，冒泡排序和簡(jiǎn)單選擇排序矗烛。這四種排序可以不太嚴(yán)謹(jǐn)?shù)亩x為八種排序算法中的較簡(jiǎn)單的排序算法辅柴，接下來(lái)就要介紹的就是比較復(fù)雜的排序算法，所謂的復(fù)雜其實(shí)指的就是算法的思想上，實(shí)現(xiàn)的邏輯上要復(fù)雜一些碌嘀。但是萬(wàn)變不離其宗碾篡，大量的代碼也許換來(lái)的僅僅是很小的效率的提升，但是千里之堤毀于蟻穴筏餐，往往是這些小小的細(xì)節(jié)會(huì)趕走大量的用戶，這個(gè)損失是不可估量的牡拇。又說(shuō)跑題了魁瞪，回到正題繼續(xù)介紹今天的主角：希爾排序。
可能大家在看到之前幾個(gè)排序算法的時(shí)候惠呼，通過(guò)它名字就可以比較形象的猜出這個(gè)排序算法的主要特征导俘，甚至是核心的思想。但是今天要介紹的是八大排序算法中唯一一個(gè)以發(fā)明者的名字命名的排序算法剔蹋。在物理學(xué)旅薄，數(shù)學(xué)中，以科學(xué)家名字命名的公式泣崩，定義真的是數(shù)不勝數(shù)少梁，就牛頓牛老師的名字在我學(xué)過(guò)的知識(shí)中就出現(xiàn)了五六次，力的單位牛頓矫付；牛頓一二三定律凯沪；牛頓萊布尼茨方程等等。但是可能大家可能沒(méi)有注意买优，在計(jì)算機(jī)領(lǐng)域中妨马，以大師的人名命名的算法包括發(fā)明真的是少之又少∩庇“約翰·阿塔那索夫”這個(gè)人名可能很多人甚至是同行們都很陌生烘跺，簡(jiǎn)單的介紹一下，這個(gè)人是第一個(gè)發(fā)明現(xiàn)代電子計(jì)算機(jī)的人脂崔，也被成為“電子計(jì)算機(jī)之父”滤淳。我覺(jué)得約翰·阿塔那索夫教授所做出的貢獻(xiàn)絕對(duì)應(yīng)該和愛(ài)迪生，牛頓砌左，瓦特等大師一樣被人們牢記娇钱，但是甚至對(duì)他的名字大家都知之甚少。直到前幾年绊困，模仿游戲那部電影上映才讓大家認(rèn)識(shí)了“計(jì)算機(jī)之父”圖靈的故事文搂，我覺(jué)得這個(gè)現(xiàn)象真的很讓我困惑。也許甚至是那樣偉大的科學(xué)家靈魂里也都或多或少具有著一個(gè)程序員低調(diào)不善言辭的性格吧秤朗。
希爾排序煤蹭，是由Donald Shell于1959年提出的。它作為插入排序的一種，對(duì)直接插入排序進(jìn)行了很大的優(yōu)化硝皂，由于直接插入排序在每次和之前的元素進(jìn)行比較的時(shí)候如果符合條件就要進(jìn)行插入操作常挚，這樣做稽物，如果這樣會(huì)造成較遠(yuǎn)的元素需要很多次的無(wú)用交換才能放到正確的位置，這樣的效率是很低的贝或。 希爾排序會(huì)首先比較較遠(yuǎn)的元素，這樣可以使離正確位置很遠(yuǎn)的元素很快的回到合適的位置咪奖〉脸溃可能有人會(huì)問(wèn)，這不是多此一舉嗎趟佃，正常執(zhí)行直接插入排序就好了，還多整一步闲昭。關(guān)于這個(gè)疑惑，我舉一個(gè)簡(jiǎn)單例子靡挥，大家應(yīng)該就能理解這一步的巧妙之處了汤纸。新生報(bào)到的時(shí)候大家互相不認(rèn)識(shí)，排成一列站隊(duì)的時(shí)候也是高矮胖瘦芹血，參差不齊。這個(gè)時(shí)候的隊(duì)列就很像待排序的數(shù)組幔烛。這個(gè)時(shí)候老師來(lái)了，小個(gè)在前大個(gè)在后排隊(duì)令蛉，這個(gè)時(shí)候狡恬，比如說(shuō)隊(duì)尾站的恰巧是個(gè)字很小的同學(xué)，如果按直接插入排序的思想的邏輯弟劲，老師會(huì)從前到后，依次進(jìn)行排序兔乞，當(dāng)遍歷到隊(duì)尾的時(shí)候才會(huì)對(duì)他進(jìn)行排序凉唐，如果隊(duì)伍20個(gè)人霍骄，他就要移動(dòng)二十次。但是在正常情況下簿训，老師如果發(fā)現(xiàn)隊(duì)尾有一個(gè)或幾個(gè)小個(gè)子米间，會(huì)馬上把他們叫到前面，把排頭幾個(gè)大個(gè)子調(diào)到隊(duì)尾车伞，這就是希爾排序的巧妙之處喻喳。接下來(lái)就是這個(gè)算法的詳細(xì)介紹和實(shí)現(xiàn)。
首先谦去，這個(gè)算法引入了一個(gè)新的概念蹦哼，叫做步長(zhǎng)。在希爾排序中需要把整個(gè)元素分成N組纲熏，而這個(gè)步長(zhǎng)決定著具體分幾組，也就是說(shuō)勺拣，哪個(gè)元素和距離他長(zhǎng)度+步長(zhǎng)的元素為一組。舉個(gè)例子药有，一個(gè)數(shù)組：[5,4,3,2,1]，如果步長(zhǎng)為3苹丸，五個(gè)元素步長(zhǎng)為3，首先[5,2]一組宦言，[4,1]一組商模，[3]一組令花。而分組之后組內(nèi)進(jìn)行直接插入排序凉倚。組內(nèi)的元素變?yōu)?[2,5],[1,4],[3]。然很關(guān)鍵稽寒，將元素復(fù)位，[2,1,3,5,4]慎王。然后把步長(zhǎng)設(shè)為2宏侍，[2,3,4]一組，[1,5]一組谅河。最后，將步長(zhǎng)設(shè)為1的時(shí)候吐限，就是我們熟悉的直接插入排序了褂始，前面的步驟的目的就是將較遠(yuǎn)的元素通過(guò)盡可能少的步驟移動(dòng)到正確的位置，在最后步長(zhǎng)為一的時(shí)候執(zhí)行一次直接插入操作崎苗，這時(shí)的數(shù)組基本上只需要移動(dòng)很少的次數(shù)就能實(shí)現(xiàn)最終的排序。這就是希爾排序的全部過(guò)程脑奠，在執(zhí)行直接插入排序之前幅慌，對(duì)整個(gè)數(shù)組進(jìn)行優(yōu)化。接下來(lái)進(jìn)行代碼實(shí)現(xiàn)胰伍。
1骂租、設(shè)置步長(zhǎng)
var step = 1;
var l = arr.length;
while(step<l/3){h=h*3;}
希爾排序和直接插入排序的區(qū)別就是引入了步長(zhǎng)的概念，步長(zhǎng)如何選擇就變得很關(guān)鍵了渗饮，關(guān)于取步長(zhǎng)的算法就完全可以長(zhǎng)篇大論的討論很久宿刮。這里就不贅述了私蕾，鑒于較小的數(shù)據(jù)量，這里我取步長(zhǎng)為：3,1磕潮。如果數(shù)據(jù)量很大容贝，可以將步長(zhǎng)設(shè)為5，3斤富， 1或者7, 5， 3焕参， 1.這里關(guān)于步長(zhǎng)的取法就不多說(shuō)了脚囊。
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行代碼其實(shí)就是希爾排序的核心實(shí)現(xiàn)桐磁，可能有的人會(huì)覺(jué)得似曾相識(shí)，和直接插入排序有點(diǎn)像啊衬以。沒(méi)錯(cuò)校摩，當(dāng)步長(zhǎng)step為1的時(shí)候，執(zhí)行的就是直接插入排序衙吩。步長(zhǎng)大于1的時(shí)候?qū)Ξ?dāng)前元素和距離加上步長(zhǎng)的元素進(jìn)行比較，如果前面的元素大于后面的元素冯勉，那么執(zhí)行交換操作摹芙。然后步長(zhǎng)減小，直到步長(zhǎng)為1浮禾，執(zhí)行直接插入操作。
這就是希爾排序的全部介紹杯活。感謝閱讀。
