laravel 先排序后分组怎么写_插入排序的故事
生活随笔
收集整理的這篇文章主要介紹了
laravel 先排序后分组怎么写_插入排序的故事
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
話說計(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)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 拼音开头有什么字_语文基础 孩子刚上一年
- 下一篇: matlab偶极矩电场强度分布图_物理-