插入排序的故事

話說(shuō)計(jì)算機(jī)世界有一個(gè)誠(chéng)實(shí)國(guó)拯爽，那里的人們不但誠(chéng)實(shí)培己，而且尊老碳蛋，每次排隊(duì)都讓年紀(jì)大的人排前面。

有一次小胖到誠(chéng)實(shí)國(guó)去旅游省咨，肚子餓了想吃東西肃弟，發(fā)現(xiàn)一個(gè)燒餅店門前有人排著隊(duì)，他就跟在隊(duì)伍后面一起排隊(duì)零蓉。沒(méi)過(guò)多久笤受，又來(lái)了一個(gè)人，站在小胖后面敌蜂，并問(wèn)他：“小伙子箩兽，你今年多大？”

“26章喉，怎么啦汗贫？”

“26？那你得排在我后面秸脱，我今年38啦落包。”

“為什么撞反？明明是我先來(lái)的妥色，先來(lái)后到你不懂嗎？”

“哈哈遏片，先來(lái)后到嘹害？小伙子你是外地來(lái)旅游的吧，還不知道我們這的規(guī)矩吮便。我們誠(chéng)實(shí)國(guó)人不僅誠(chéng)實(shí)笔呀，而且尊老，排隊(duì)都讓年紀(jì)大的人排前面髓需。我比你大许师，所以要排在你前面唯灵≡痴牵”

“原來(lái)是這樣赌渣！對(duì)了功蜓，在我前面是一個(gè)小孩锋勺，那我也可以先插到他前面去咯宫患？”

“是的唁盏，你先往前面插隊(duì)绪钥，等你弄好了松申，我再來(lái)云芦「┯猓”

“還有這種神操作！謝謝你提醒我熬艘荨桌肴！我要向前去了×鹄”

此時(shí)小胖所站位置如圖示：(地面下方的序號(hào)表示每個(gè)人所在的位置坠七，用0-5表示；人體身上的數(shù)字表示其年齡善已。紅臉的是小胖灼捂，他26歲，站在5號(hào)位置)

小胖拍了拍前面少年的肩膀换团，問(wèn)他：“小朋友悉稠，今年幾歲了？”

“叔叔艘包，我今年12歲的猛。”

“那請(qǐng)你讓一讓想虎，叔叔我今年26了卦尊。”

“好的舌厨∑袢矗”

于是二人換了位置。此時(shí)站在小胖前面的是一個(gè)瘦瘦高高的年輕人裙椭，戴著一副眼鏡躏哩，小胖也吃不準(zhǔn)他有多大年紀(jì)，就小心翼翼地問(wèn)他：“兄弟我今年26揉燃，請(qǐng)問(wèn)你多大了扫尺？”

“25”，瘦子一邊回答一邊默默地站到小胖后面去了炊汤。

此時(shí)站在小胖前面的是一個(gè)跟他長(zhǎng)得差不多的胖墩正驻，小胖熱情地和他打招呼：“嗨，兄弟抢腐，哥哥我今年26姑曙，你呢？”

“26奥醣丁渣磷？那跟在我后面吧，哥哥我今年也正好26歲授瘦〈捉纾”

此時(shí)小胖所站位置如圖示：

如果我們用Python語(yǔ)言描述小胖插隊(duì)的過(guò)程，應(yīng)該是這樣：

lst = [60,40,26,25,12,25]#小胖插隊(duì)前的站隊(duì)情況

age = 26 #小胖的年齡

pos = 5? #小胖的初始位置序號(hào)

while pos > 0: #不斷詢問(wèn)前面的人提完，直到到達(dá)隊(duì)伍前端

? ? if lst[pos-1] < age: #若前面的人比小胖小形纺，則后退一位（相當(dāng)于和小胖交換了位置）

? ? ? ? lst[pos] = lst[pos-1]

? ? ? ? pos -= 1 #繼續(xù)向前詢問(wèn)下一個(gè)人

? ? else:? #否則說(shuō)明小胖找到了正確的插隊(duì)位置，退出循環(huán)

? ? ? ? break

lst[pos] = age #最終小胖站在正確的位置上

print(lst) #輸出小胖插隊(duì)后的站隊(duì)情況

幾個(gè)月后徒欣，小胖帶著女朋友花花一起去誠(chéng)實(shí)國(guó)旅游逐样，來(lái)到同一家店排隊(duì)買燒餅。正逢黃金周旅游旺季打肝，排隊(duì)的人可真多爸隆！花花看看前面長(zhǎng)長(zhǎng)的隊(duì)伍粗梭，又看了看空空的礦泉水瓶争便，對(duì)小胖撒嬌說(shuō)：“親愛(ài)的，倫家的水喝光了断医，口干舌燥滞乙，不想費(fèi)口舌和前面的人比誰(shuí)大誰(shuí)小。反正你也知道我只比你大3歲鉴嗤，要不你幫我去問(wèn)斩启，找到正確的位置后，站在那人旁邊醉锅，給我發(fā)個(gè)信號(hào)兔簇，然后我叫前面的人給我挪出位置，就可以直接走過(guò)去了硬耍。用Python語(yǔ)言表示就是這樣垄琐。”

#將值為age的元素插入到非遞增列表lst中默垄，并保持列表的有序性

def insert(lst,age):

? ? pos = insert_pos(lst,0,len(lst)-1,age) #小胖幫花花查找插隊(duì)的位置

? ? lst.append(age) #花花先站在隊(duì)伍的后面此虑，使得列表的長(zhǎng)度加1

? ? for i in range(len(lst)-1,pos,-1):#人們逐個(gè)后移，為花花騰出插入位置

? ? ? ? lst[i] = lst[i-1]

? ? lst[pos] = age #最終花花站在正確的位置上

“知道了口锭，不就是幫你找到正確的插入位置嗎朦前。沒(méi)問(wèn)題，看我的鹃操【麓纾”

小胖去了，他很賣力氣荆隘，逐個(gè)詢問(wèn)排隊(duì)人的年齡恩伺。半個(gè)小時(shí)過(guò)去了，小胖還在問(wèn)椰拒，花花等得有些不耐煩了晶渠。又過(guò)了十幾分鐘凰荚，小胖終于在遠(yuǎn)處朝花花揮手了，花花知道他已經(jīng)找到正確位置了褒脯。于是花花依次跟排隊(duì)的人說(shuō)：“不好意思便瑟，我男朋友幫我找到了正確的插入位置，是在你前面番川，麻煩你往后退一步到涂，幫我騰個(gè)位置出來(lái)“涠剑”

大家都照著做了践啄，沒(méi)過(guò)多久花花就站在了自己的位置上，她對(duì)小胖表示感謝沉御，但是又有些不滿意地說(shuō)：“你是怎么搞的屿讽，怎么花了這么長(zhǎng)時(shí)間？”

小胖訴苦說(shuō)：“花花你是不知道嚷节，排隊(duì)的人實(shí)在太多了聂儒，而且來(lái)自世界各地，說(shuō)什么話的人都有硫痰，我是使盡了渾身解數(shù)才找到這個(gè)正確位置的榜没椤！”

“是嗎效斑？那你告訴我你是怎么做的非春？”

“還能怎么做？一個(gè)個(gè)問(wèn)過(guò)來(lái)唄缓屠，我還是用Python語(yǔ)言寫個(gè)函數(shù)給你看吧奇昙。”

#順序查找age的插入位置敌完，left和right是非遞增列表lst的左右邊界

def insert_pos(lst,left,right,age):

? ? pos = right+1 #花花的初始位置序號(hào)

? ? #不斷詢問(wèn)前面人的年齡储耐，直到到達(dá)隊(duì)伍前端或遇到不小于花花的人

? ? while pos > left and lst[pos-1] < age:

? ? ? ? pos -= 1

? ? return pos #返回正確的插入位置

“原來(lái)你是用順序查詢的辦法啊，怪不得這么慢滨溉。前面的隊(duì)伍都已經(jīng)是有序的了什湘，難道你就不能動(dòng)動(dòng)腦子嗎？”

“動(dòng)動(dòng)腦子晦攒？哦闽撤，我想起來(lái)了，前面隊(duì)伍有序脯颜，我可以用折半查找法尋找插入位置哟旗，這樣速度可以快上很多！”

“現(xiàn)在才想到，剛才干什么吃的去了闸餐！真是個(gè)豬腦袋饱亮！罰你用Python語(yǔ)言把折半查找插入位置的函數(shù)給我寫出來(lái)∫锞蓿”

“夫人近尚，遵命！”

#折半查找age的插入位置,left和right是非遞增列表lst的左右邊界

def binary_insert_pos(lst,left,right,age):

? ? while left <= right:

? ? ? ? mid = (left + right) // 2

? ? ? ? if age > lst[mid]:? #中間值小于age场勤，則插入位置在左半邊

? ? ? ? ? ? right = mid - 1

? ? ? ? else: #否則插入位置在右半邊

? ? ? ? ? ? left = mid + 1

? ? return left #返回正確的插入位置

小胖從誠(chéng)實(shí)國(guó)回來(lái)，剛好趕上公司給大家發(fā)獎(jiǎng)金歼跟，大家在財(cái)會(huì)室門口擠作一團(tuán)和媳，領(lǐng)導(dǎo)看不下去了，讓小胖幫忙組織大伙把隊(duì)伍排好哈街。小胖想起來(lái)自己在誠(chéng)實(shí)國(guó)排隊(duì)買燒餅的經(jīng)歷留瞳，就依葫蘆畫瓢，很快把隊(duì)伍排好了骚秦。

領(lǐng)導(dǎo)看了非常滿意她倘，問(wèn)小胖怎么做到的。

小胖很謙虛地回答：“其實(shí)也很簡(jiǎn)單作箍，我這是借鑒了誠(chéng)實(shí)國(guó)人排隊(duì)的方法硬梁。先隨便找一個(gè)人排在最前面，然后第二個(gè)人跟在他后面胞得，如果第二個(gè)人比第一個(gè)人大荧止，就插隊(duì)到前面，否則不動(dòng)阶剑。這樣前兩個(gè)人是有序的跃巡。接下來(lái)第三個(gè)人用同樣的方法插隊(duì)，找到正確的位置牧愁，這樣前三個(gè)人是有序的素邪。采用同樣的方法，把后面的人一個(gè)個(gè)插入猪半，直到隊(duì)伍全部有序兔朦。”

“嗯嗯办龄，不錯(cuò)烘绽，你用Python語(yǔ)言把程序?qū)懗鰜?lái)吧，我要把這個(gè)好辦法推廣到全公司俐填“步樱”

“領(lǐng)導(dǎo)，遵命！”

#直接插入排序算法

def insert_sort(lst):

? ? for i in range(1,len(lst)): #從第二個(gè)元素開(kāi)始插入排序

? ? ? ? t = lst[i]?

? ? ? ? j = i?

? ? ? ? while j > 0 and lst[j-1] < t: #一邊比較一邊向后退騰出位置

? ? ? ? ? ? lst[j] = lst[j-1]?

? ? ? ? ? ? j -= 1?

? ? ? ? lst[j] = t

#折半查找插入排序算法

def binary_insert_sort(lst):

? ? for i in range(1,len(lst)): #從第二個(gè)元素開(kāi)始插入排序

? ? ? ? t = lst[i]

? ? ? ? pos = binary_insert_pos(lst,0,i-1,lst[i]) #調(diào)用前面的折半查找插入位置函數(shù)

? ? ? ? for i in range(i,pos,-1): #元素后移盏檐，為t騰出插入位置

? ? ? ? ? ? lst[i] = lst[i-1]

? ? ? ? lst[pos] = t?

幾十年過(guò)去了歇式，此時(shí)的小胖已是排序界的高手，插入排序算法運(yùn)用得爐火純青胡野。幾十年的排序經(jīng)驗(yàn)讓他認(rèn)識(shí)到插入排序在對(duì)“基本有序”的數(shù)據(jù)操作時(shí)材失，效率非常高，都快趕上線性排序的效率了（所謂“基本有序”是指待排序的數(shù)組逆序數(shù)比較少）硫豆。但進(jìn)行插入操作時(shí)龙巨，每次只能將數(shù)據(jù)移動(dòng)一位，難免出現(xiàn)大量重復(fù)移動(dòng)熊响。例如在誠(chéng)實(shí)國(guó)排隊(duì)的時(shí)候旨别，小孩子就特別受累，每次后面來(lái)一個(gè)人汗茄，他們就要后退一步秸弛，所以有些小孩索性直接一次性多退幾步，讓后來(lái)的人直接站到他前面去洪碳。

小胖因此得到啟發(fā)递览，如果將元素盡可能快的移動(dòng)到它“該去”的地方，肯定會(huì)減少重復(fù)移動(dòng)的次數(shù)瞳腌，提高效率绞铃。小胖的想法是把全部元素分組排序，將所有距離為步長(zhǎng)gap的元素放在同一個(gè)組中纯趋，通過(guò)“跳躍式移動(dòng)”的方法憎兽，能讓元素每次移動(dòng)一大步，即步長(zhǎng)gap>1吵冒，大大提高了移動(dòng)的效率纯命。一趟排序下來(lái)，雖然同組的元素沒(méi)有挨在一起痹栖，各組元素相互隔開(kāi)亿汞，但是由于每一組都已經(jīng)各自排好序了，所以整個(gè)序列的“有序性”還是變好了揪阿。

我們來(lái)看一個(gè)例子：

圖1是原始序列疗我，序列長(zhǎng)度len=8，我們先取步長(zhǎng)gap=len/2=4南捂，把序列分成4組（容易看出來(lái)吴裤，分組數(shù)量和步長(zhǎng)相等）。地面下方的序號(hào)表示每個(gè)人所在的位置溺健，用0-7表示麦牺；人體身上的數(shù)字表示其年齡，人體頭部的顏色相同表示他們?cè)谕唤M，此時(shí)分組情況為（0,4）剖膳，（1,5）魏颓，（2,6），（3,7）吱晒。

我們對(duì)同組的人進(jìn)行簡(jiǎn)單插入排序甸饱，結(jié)果如圖2所示。一趟排序下來(lái)仑濒，雖然同組的元素沒(méi)有挨在一起叹话，各組元素相互隔開(kāi)，但是由于每一組都已經(jīng)各自排好序了躏精，所以整個(gè)序列看上去還是比以前要“有序”些渣刷，即逆序數(shù)要少一些。

接下來(lái)我們?nèi)「〉牟介L(zhǎng)gap=2矗烛，把序列分成2組，此時(shí)分組情況為（0,2箩溃，4瞭吃，6），（1,3涣旨，5歪架，7）。各元素位置和分組情況如圖3所示：

我們對(duì)同組的人進(jìn)行簡(jiǎn)單插入排序霹陡，結(jié)果如圖4所示和蚪。很明顯，現(xiàn)在逆序數(shù)又少了很多烹棉，整個(gè)序列變得更加“有序”了攒霹。

同樣的，我們繼續(xù)減少步長(zhǎng)浆洗，取gap=1催束，把序列分成1組，此時(shí)各元素位置和分組情況如圖5所示：

現(xiàn)在步長(zhǎng)gap=1伏社，就是普通的插入排序】俅蹋現(xiàn)在整個(gè)序列已經(jīng)是“基本有序”了，直接插入排序也能高效完成摘昌。排序結(jié)果如圖6所示：

通過(guò)上面的例子我們可以看到速妖，將相隔一定步長(zhǎng)的元素組成一個(gè)子序列，分別對(duì)他們進(jìn)行插入排序聪黎，可以實(shí)現(xiàn)跳躍式的移動(dòng)罕容，使得排序的效率提高。經(jīng)過(guò)一輪分組排序后，雖然整個(gè)序列還是無(wú)序的杀赢，但每個(gè)相互隔開(kāi)的子序列已經(jīng)變得有序烘跺，總的逆序數(shù)減少，整個(gè)序列變得更加“有序”了脂崔。每完成一輪分組排序后滤淳，我們就將步長(zhǎng)減半，繼續(xù)分組排序砌左，直至步長(zhǎng)step=1脖咐，就變成普通的插入排序了。由于此時(shí)整個(gè)序列已經(jīng)“基本有序”了汇歹，直接插入排序也能高效完成屁擅。

這種另類的插入排序算法就是傳說(shuō)中的“希爾排序”。用Python語(yǔ)言實(shí)現(xiàn)代碼如下：

#希爾排序

def shell_sort(lst):

? ? gap = len(lst) // 2

? ? while gap > 0:

? ? ? ? for i in range(gap,len(lst)): #將相隔為step的元素組成一個(gè)子序列产弹，分別對(duì)各組進(jìn)行插入排序

? ? ? ? ? ? t = lst[i]

? ? ? ? ? ? j = i

? ? ? ? ? ? while j >= gap and lst[j-gap] > t: #跳躍插入派歌，跳躍距離為gap

? ? ? ? ? ? ? ? lst[j] = lst[j-gap]

? ? ? ? ? ? ? ? j -= gap

? ? ? ? ? ? lst[j] = t

? ? ? ? gap //= 2 #步長(zhǎng)gap每次減半

希爾排序的關(guān)鍵在于不能將元素隨便分組后各自排序，而是將相隔一定步長(zhǎng)的元素組成一個(gè)子序列痰哨，實(shí)現(xiàn)跳躍式的移動(dòng)胶果，使得排序的效率提高。

步長(zhǎng)的選擇是希爾排序的重要部分斤斧。前面的算法中早抠，我們讓步長(zhǎng)step每次減半，這是最簡(jiǎn)單的方法撬讽，但不是唯一的方法蕊连。事實(shí)上只要滿足讓步長(zhǎng)逐漸減小，最終步長(zhǎng)為1的規(guī)則游昼，無(wú)論采用何種遞減規(guī)律都可以甘苍。算法最開(kāi)始以某個(gè)步長(zhǎng)進(jìn)行排序，然后會(huì)繼續(xù)以更小的步長(zhǎng)排序酱床，最終算法以步長(zhǎng)為1排序羊赵。當(dāng)步長(zhǎng)為1時(shí)，算法變?yōu)椴迦肱判蛏纫ィ@就保證了數(shù)據(jù)一定會(huì)被排序昧捷。

Donald Shell 最初建議選擇步長(zhǎng)step=n/2，然后讓步長(zhǎng)step每次減半罐寨，直到步長(zhǎng)step=1靡挥。雖然這樣取可以比O(n^2)類的算法（插入排序）更好，但這樣仍然有減少平均時(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í)間完成排序了盆赤。

已知的最好步長(zhǎng)序列是由Sedgewick提出的 (1, 5, 19, 41, 109,...)贾富，該序列的項(xiàng)來(lái)自 9 * 4^i - 9 * 2^i + 1 和 4^i - 3 * 2^i + 1 這兩個(gè)算式。這項(xiàng)研究也表明在希爾排序中比較是最主要的操作牺六，而不是交換颤枪。用這種步長(zhǎng)序列的希爾排序比插入排序和堆排序都要快，甚至在小數(shù)組中比快速排序還快淑际，但是在涉及大量數(shù)據(jù)時(shí)希爾排序還是比快速排序慢畏纲。

另一個(gè)在大數(shù)組中表現(xiàn)優(yōu)異的步長(zhǎng)序列是(斐波那契數(shù)列除去0和1將剩余的數(shù)以黃金分區(qū)比的兩倍的冪進(jìn)行運(yùn)算得到的數(shù)列)：（1, 9, 34,182, 836, 4025, 19001, 90358,428481, 2034035, 9651787, 45806244, 217378076,1031612713, …）。