話說計(jì)算機(jī)世界有一個誠實(shí)國，那里的人們不但誠實(shí)，而且尊老，每次排隊(duì)都讓年紀(jì)大的人排前面。

有一次小胖到誠實(shí)國去旅游，肚子餓了想吃東西，發(fā)現(xiàn)一個燒餅店門前有人排著隊(duì)，他就跟在隊(duì)伍后面一起排隊(duì)。沒過多久，又來了一個人，站在小胖后面，并問他：“小伙子，你今年多大？”“26，怎么啦？”“26？那你得排在我后面，我今年38啦。”“為什么？明明是我先來的，先來后到你不懂嗎？”“哈哈，先來后到？小伙子你是外地來旅游的吧，還不知道我們這的規(guī)矩。我們誠實(shí)國人不僅誠實(shí)，而且尊老，排隊(duì)都讓年紀(jì)大的人排前面。我比你大，所以要排在你前面?！薄霸瓉硎沁@樣！對了，在我前面是一個小孩，那我也可以先插到他前面去咯？”“是的，你先往前面插隊(duì)，等你弄好了，我再來?！薄斑€有這種神操作！謝謝你提醒我啊！我要向前去了?！贝藭r(shí)小胖所站位置如圖示：(地面下方的序號表示每個人所在的位置，用0-5表示；人體身上的數(shù)字表示其年齡。紅臉的是小胖，他26歲，站在5號位置)小胖拍了拍前面少年的肩膀，問他：“小朋友，今年幾歲了？”“叔叔，我今年12歲?！薄澳钦埬阕屢蛔?#xff0c;叔叔我今年26了?！薄昂玫??！庇谑嵌藫Q了位置。此時(shí)站在小胖前面的是一個瘦瘦高高的年輕人，戴著一副眼鏡，小胖也吃不準(zhǔn)他有多大年紀(jì)，就小心翼翼地問他：“兄弟我今年26，請問你多大了？”“25”，瘦子一邊回答一邊默默地站到小胖后面去了。此時(shí)站在小胖前面的是一個跟他長得差不多的胖墩，小胖熱情地和他打招呼：“嗨，兄弟，哥哥我今年26，你呢？”“26啊？那跟在我后面吧，哥哥我今年也正好26歲?！贝藭r(shí)小胖所站位置如圖示：如果我們用Python語言描述小胖插隊(duì)的過程，應(yīng)該是這樣：lst = [60,40,26,25,12,25]#小胖插隊(duì)前的站隊(duì)情況age = 26 #小胖的年齡pos = 5 #小胖的初始位置序號while pos > 0: #不斷詢問前面的人，直到到達(dá)隊(duì)伍前端 if lst[pos-1] < age: #若前面的人比小胖小，則后退一位(相當(dāng)于和小胖交換了位置) lst[pos] = lst[pos-1] pos -= 1 #繼續(xù)向前詢問下一個人 else: #否則說明小胖找到了正確的插隊(duì)位置，退出循環(huán) breaklst[pos] = age #最終小胖站在正確的位置上print(lst)?#輸出小胖插隊(duì)后的站隊(duì)情況幾個月后，小胖帶著女朋友花花一起去誠實(shí)國旅游，來到同一家店排隊(duì)買燒餅。正逢黃金周旅游旺季，排隊(duì)的人可真多啊！花花看看前面長長的隊(duì)伍，又看了看空空的礦泉水瓶，對小胖撒嬌說：“親愛的，倫家的水喝光了，口干舌燥，不想費(fèi)口舌和前面的人比誰大誰小。反正你也知道我只比你大3歲，要不你幫我去問，找到正確的位置后，站在那人旁邊，給我發(fā)個信號，然后我叫前面的人給我挪出位置，就可以直接走過去了。用Python語言表示就是這樣?！?將值為age的元素插入到非遞增列表lst中，并保持列表的有序性def insert(lst,age): pos = insert_pos(lst,0,len(lst)-1,age) #小胖幫花花查找插隊(duì)的位置 lst.append(age) #花花先站在隊(duì)伍的后面，使得列表的長度加1 for i in range(len(lst)-1,pos,-1):#人們逐個后移，為花花騰出插入位置 lst[i] = lst[i-1]????lst[pos]?=?age?#最終花花站在正確的位置上“知道了，不就是幫你找到正確的插入位置嗎。沒問題，看我的?！毙∨秩チ?#xff0c;他很賣力氣，逐個詢問排隊(duì)人的年齡。半個小時(shí)過去了，小胖還在問，花花等得有些不耐煩了。又過了十幾分鐘，小胖終于在遠(yuǎn)處朝花花揮手了，花花知道他已經(jīng)找到正確位置了。于是花花依次跟排隊(duì)的人說：“不好意思，我男朋友幫我找到了正確的插入位置，是在你前面，麻煩你往后退一步，幫我騰個位置出來。”大家都照著做了，沒過多久花花就站在了自己的位置上，她對小胖表示感謝，但是又有些不滿意地說：“你是怎么搞的，怎么花了這么長時(shí)間？”小胖訴苦說：“花花你是不知道，排隊(duì)的人實(shí)在太多了，而且來自世界各地，說什么話的人都有，我是使盡了渾身解數(shù)才找到這個正確位置的啊！”“是嗎？那你告訴我你是怎么做的？”“還能怎么做？一個個問過來唄，我還是用Python語言寫個函數(shù)給你看吧?！?順序查找age的插入位置，left和right是非遞增列表lst的左右邊界def insert_pos(lst,left,right,age): pos = right+1 #花花的初始位置序號 #不斷詢問前面人的年齡，直到到達(dá)隊(duì)伍前端或遇到不小于花花的人 while pos > left and lst[pos-1] < age: pos -= 1????return?pos?#返回正確的插入位置“原來你是用順序查詢的辦法啊，怪不得這么慢。前面的隊(duì)伍都已經(jīng)是有序的了，難道你就不能動動腦子嗎？”“動動腦子？哦，我想起來了，前面隊(duì)伍有序，我可以用折半查找法尋找插入位置，這樣速度可以快上很多！”“現(xiàn)在才想到，剛才干什么吃的去了！真是個豬腦袋！罰你用Python語言把折半查找插入位置的函數(shù)給我寫出來。”“夫人，遵命！”#折半查找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?#返回正確的插入位置小胖從誠實(shí)國回來，剛好趕上公司給大家發(fā)獎金，大家在財(cái)會室門口擠作一團(tuán)，領(lǐng)導(dǎo)看不下去了，讓小胖幫忙組織大伙把隊(duì)伍排好。小胖想起來自己在誠實(shí)國排隊(duì)買燒餅的經(jīng)歷，就依葫蘆畫瓢，很快把隊(duì)伍排好了。領(lǐng)導(dǎo)看了非常滿意，問小胖怎么做到的。小胖很謙虛地回答：“其實(shí)也很簡單，我這是借鑒了誠實(shí)國人排隊(duì)的方法。先隨便找一個人排在最前面，然后第二個人跟在他后面，如果第二個人比第一個人大，就插隊(duì)到前面，否則不動。這樣前兩個人是有序的。接下來第三個人用同樣的方法插隊(duì)，找到正確的位置，這樣前三個人是有序的。采用同樣的方法，把后面的人一個個插入，直到隊(duì)伍全部有序?！薄班培?#xff0c;不錯，你用Python語言把程序?qū)懗鰜戆?#xff0c;我要把這個好辦法推廣到全公司。”“領(lǐng)導(dǎo)，遵命！”#直接插入排序算法def insert_sort(lst): for i in range(1,len(lst)): #從第二個元素開始插入排序 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)): #從第二個元素開始插入排序 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?幾十年過去了，此時(shí)的小胖已是排序界的高手，插入排序算法運(yùn)用得爐火純青。幾十年的排序經(jīng)驗(yàn)讓他認(rèn)識到插入排序在對“基本有序”的數(shù)據(jù)操作時(shí)，效率非常高，都快趕上線性排序的效率了(所謂“基本有序”是指待排序的數(shù)組逆序數(shù)比較少)。但進(jìn)行插入操作時(shí)，每次只能將數(shù)據(jù)移動一位，難免出現(xiàn)大量重復(fù)移動。例如在誠實(shí)國排隊(duì)的時(shí)候，小孩子就特別受累，每次后面來一個人，他們就要后退一步，所以有些小孩索性直接一次性多退幾步，讓后來的人直接站到他前面去。小胖因此得到啟發(fā)，如果將元素盡可能快的移動到它“該去”的地方，肯定會減少重復(fù)移動的次數(shù)，提高效率。小胖的想法是把全部元素分組排序，將所有距離為步長gap的元素放在同一個組中，通過“跳躍式移動”的方法，能讓元素每次移動一大步，即步長gap>1，大大提高了移動的效率。一趟排序下來，雖然同組的元素沒有挨在一起，各組元素相互隔開，但是由于每一組都已經(jīng)各自排好序了，所以整個序列的“有序性”還是變好了。我們來看一個例子：圖1是原始序列，序列長度len=8，我們先取步長gap=len/2=4，把序列分成4組(容易看出來，分組數(shù)量和步長相等)。地面下方的序號表示每個人所在的位置，用0-7表示；人體身上的數(shù)字表示其年齡，人體頭部的顏色相同表示他們在同一組，此時(shí)分組情況為(0,4)，(1,5)，(2,6)，(3,7)。我們對同組的人進(jìn)行簡單插入排序，結(jié)果如圖2所示。一趟排序下來，雖然同組的元素沒有挨在一起，各組元素相互隔開，但是由于每一組都已經(jīng)各自排好序了，所以整個序列看上去還是比以前要“有序”些，即逆序數(shù)要少一些。接下來我們?nèi)「〉牟介Lgap=2，把序列分成2組，此時(shí)分組情況為(0,2，4，6)，(1,3，5，7)。各元素位置和分組情況如圖3所示：我們對同組的人進(jìn)行簡單插入排序，結(jié)果如圖4所示。很明顯，現(xiàn)在逆序數(shù)又少了很多，整個序列變得更加“有序”了。同樣的，我們繼續(xù)減少步長，取gap=1，把序列分成1組，此時(shí)各元素位置和分組情況如圖5所示：現(xiàn)在步長gap=1，就是普通的插入排序?，F(xiàn)在整個序列已經(jīng)是“基本有序”了，直接插入排序也能高效完成。排序結(jié)果如圖6所示：通過上面的例子我們可以看到，將相隔一定步長的元素組成一個子序列，分別對他們進(jìn)行插入排序，可以實(shí)現(xiàn)跳躍式的移動，使得排序的效率提高。經(jīng)過一輪分組排序后，雖然整個序列還是無序的，但每個相互隔開的子序列已經(jīng)變得有序，總的逆序數(shù)減少，整個序列變得更加“有序”了。每完成一輪分組排序后，我們就將步長減半，繼續(xù)分組排序，直至步長step=1，就變成普通的插入排序了。由于此時(shí)整個序列已經(jīng)“基本有序”了，直接插入排序也能高效完成。這種另類的插入排序算法就是傳說中的“希爾排序”。用Python語言實(shí)現(xiàn)代碼如下：#希爾排序def shell_sort(lst): gap = len(lst) // 2 while gap > 0: for i in range(gap,len(lst)): #將相隔為step的元素組成一個子序列，分別對各組進(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?#步長gap每次減半希爾排序的關(guān)鍵在于不能將元素隨便分組后各自排序，而是將相隔一定步長的元素組成一個子序列，實(shí)現(xiàn)跳躍式的移動，使得排序的效率提高。步長的選擇是希爾排序的重要部分。前面的算法中，我們讓步長step每次減半，這是最簡單的方法，但不是唯一的方法。事實(shí)上只要滿足讓步長逐漸減小，最終步長為1的規(guī)則，無論采用何種遞減規(guī)律都可以。算法最開始以某個步長進(jìn)行排序，然后會繼續(xù)以更小的步長排序，最終算法以步長為1排序。當(dāng)步長為1時(shí)，算法變?yōu)椴迦肱判?#xff0c;這就保證了數(shù)據(jù)一定會被排序。Donald Shell 最初建議選擇步長step=n/2，然后讓步長step每次減半，直到步長step=1。雖然這樣取可以比O(n^2)類的算法(插入排序)更好，但這樣仍然有減少平均時(shí)間和最差時(shí)間的余地。可能希爾排序最重要的地方在于當(dāng)用較小步長排序后，以前用的較大步長仍然是有序的。比如，如果一個數(shù)列以步長5進(jìn)行了排序然后再以步長3進(jìn)行排序，那么該數(shù)列不僅是以步長3有序，而且是以步長5有序。如果不是這樣，那么算法在迭代過程中會打亂以前的順序，那就不會以如此短的時(shí)間完成排序了。已知的最好步長序列是由Sedgewick提出的 (1, 5, 19, 41, 109,...)，該序列的項(xiàng)來自 9 * 4^i - 9 * 2^i + 1 和 4^i - 3 * 2^i + 1 這兩個算式。這項(xiàng)研究也表明在希爾排序中比較是最主要的操作，而不是交換。用這種步長序列的希爾排序比插入排序和堆排序都要快，甚至在小數(shù)組中比快速排序還快，但是在涉及大量數(shù)據(jù)時(shí)希爾排序還是比快速排序慢。另一個在大數(shù)組中表現(xiàn)優(yōu)異的步長序列是(斐波那契數(shù)列除去0和1將剩余的數(shù)以黃金分區(qū)比的兩倍的冪進(jìn)行運(yùn)算得到的數(shù)列)：(1, 9, 34,182, 836, 4025, 19001, 90358,428481, 2034035, 9651787, 45806244, 217378076,1031612713, …)?！癙ython算法之旅”微信群等著你

掃碼加入“Python算法之旅”微信群，和斌哥面對面交流，更多資料和更有趣的話題等你一起來分享。

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的laravel 先排序后分组怎么写_插入排序的故事的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。