排序演算法匯總

06-23

排序演算法匯總

來自專欄自學編程之道

排序演算法是演算法中的入門級別，也是最常用的演算法，不管你是自己寫一個小項目還是做OJ題還是企業面試，總會見到它的身影。既然這麼重要，那就希望大家通過此文掌握下面幾種常見的排序演算法吧。

冒泡排序
插入排序
選擇排序
歸併排序
快速排序
希爾排序
堆排序

冒泡排序

時間複雜度 $O(n^{2})$ ，空間複雜度（指的是除原數據外的額外空間） $O(1)$

應用場景：假定你是一名排長，帶著你的一排人隨著大部隊行進，正好走到一個獨木橋時，突然傳來命令：原地整隊，每一排的人都要按身高從矮到高排列！你們排傻眼了，這個獨木橋只允許一人通過，連轉個身都難，怎麼整隊？這時，程序員出身的你靈機一動，喊道：「冒泡排序!"。可是你的士兵並不知道什麼是冒泡排序，於是你指揮道：隊尾的人看你前面的人，如果你前面的人比你高，就抱著他轉個身，調換你們兩個人的位置，調換後繼續看前一個人，如果還是比你高，就再調換位置，直到出現比你矮的人，把你的任務交給他。當任務輪到最前面的那個人時，就停止，並進入下一輪同樣的操作，我們排有8個人，要進行7輪操作。

實際的編程中應用不多，更多的是為了做題才用這種效率不高的排序演算法。

代碼：

插入排序

時間複雜度 $O(n^{2})$ ，空間複雜度 $O(1)$

應用場景：你和兩個好友打牌」鬥地主「，但是你是第一次玩撲克，不知道怎麼理牌，你的兩個好友驚叫，你竟然沒玩過打牌，太low了吧，於是他們教你，把牌摸起，按順序插到手裡扇形牌組中，你問道：怎麼插？回答：從大到小或從小到大都可以，比如9插到10的右邊，8插到9的右邊。。。程序員的你打斷他的話：直接說插入排序不就行了，瞎逼逼這麼多。

玩了很多盤」鬥地主「之後，你發現摸牌佔用的時間太多了，而且一張一張地摸很難摸到炸彈，於是你提議直接將牌分為三等分，每人拿一份。好友大呼：好提議。當你拿到牌後傻眼了，你又不知道如何將牌排序，好友罵道：跟剛才差不多，從牌中選出最大的牌放到最左邊，第二大的牌放在最大的牌的右邊，比如你把2放到最左邊，A放到2的右邊。。。程序員的你再次打斷他的話：直接說插入排序不就行了，瞎逼逼這麼多。

插入排序用於將新的數插入到某一個排好序的數組當中，或者對一個無序數組進行排序，由於每一次插入都要把插入點後面的數據往後挪一位，因此時間複雜度較高。但如果你的數據是放在鏈表中，那麼時間複雜度就變成 $O(n)$ 了，即只需要查找到插入點的時間，而不需要移動數據的時間。

代碼：

選擇排序

時間複雜度 $O(n^{2})$ ，空間複雜度 $O(1)$

應用場景：還是有一組牌讓你排序，只不過你每次只能交換兩張牌的位置，而不能將牌往後移一位（這是與插入排序的區別）

選擇排序的時間複雜度雖然也是 $O(n^{2})$ ，但效率比冒泡排序高很多，因為選擇排序不用每次比較後就交換兩個數的位置，而是找到最大或最小的數後再交換位置，而交換兩個數的位置花的時間是很多的。

代碼：

歸併排序

時間複雜度 $O(nlogn)$ ，空間複雜度 $O(n)$

應用場景：當你和你的一排人艱難地再獨木橋上完成了身高排序，上面又傳來了命令：所有排的人合併成一列，身高還是從矮到高排列。不少士兵抱怨道：又要排一遍，剛剛不是白排了嗎?程序員出生的你駁斥道：誰說白排了！排與排之間的合併就相當與歸併排序，時間複雜度為 $O(nlogn)$ ，很快就能排完！於是你又指揮道：一排戰在道路左側，二排站在道路右側，中間空出來，每排出來一個隊首的人，兩個人高矮比較，矮的那個人排到中間空出來的位置，同時他所在的那一排再派出隊首的人，與剛才高的那個人高矮比較，直到有一排的人全部比較完了，那麼另一排剩下的人全部站到中間的隊列後面去。

歸併排序時間複雜度較低，空間複雜度為 $O(n)$ 是因為要一個額外的數組來存合併後的數據，就像應用場景中空出中間的位置一樣。

代碼：

快速排序

時間複雜度 $O(nlogn)$ ，空間複雜度 $O(nlog2n)$ ~ $O(n)$

應用場景：你的老闆要你為1億條數據排序，在三天後提交排好序的數據，想到你剛學完冒泡排序，於是你高高興興地回去做了，你只花了一個小時就把程序寫了出來，調試發現一個bug也沒有，你呵呵一笑，這tm太簡單了。於是你開開心心地讓程序去跑了。為了慶祝一下，你晚上去吃了大餐，還用的了三天，回去我就把數據交給老闆！回到家迫不及待地查看了下電腦，發現程序還在跑，看來1億數據量還挺大的嘛，晚上再等一晚，明天肯定跑完！你自信地笑笑。。。三天後，你抱著跑得發燙的電腦交給老闆：老闆，馬上、馬上就。。。就出結果了！老闆問你用什麼演算法，你回答：冒泡排序。老闆嘆了一口氣，只見他接過你的電腦，手指在鍵盤上飛快敲擊，十分鐘後寫完程序，沒有調試就直接開始運行，3分鐘後數據處理完畢。老闆拔下U盤，說：你可以走了。你沮喪地準備離開，卻突然一驚，問道：老闆你是要我往哪裡去。老闆說：你被辭職了。你心有不甘，哭著說：再給我十分鐘，十分鐘後程序一定跑完！老闆意味深長的說：我用的是快速排序，時間複雜度為 $O(nlogn)$ ，你冒泡排序 $O(n^{2})$ ，處理1億條數據你的用時將會是我的 $n^{2}div(nlogn)$ 倍，也就是12500000倍，保守估計時間為70年。

當了多年的排長，你終於陞官了，變成了連長，你發現管理的兵多了，排序越來越麻煩。直到有一天你接觸到了快速排序演算法。你立即召集整個連的士兵，準備大顯身手。你隨機叫出一名士兵對他說，你把隊伍分成兩部分，一部分全比你高，另一部分全比你矮，我叫集合的時候你就讓比你矮的那一部分全部站到你前面，比你高的那一部分全部站到你後面。這個士兵撓撓頭，完全跟不上你這個程序員出身的思路。你接著說，做完這一切後你就站著不要動，只需要讓你前面和後面的兩個人重複你做的事情，把前面的隊伍分為兩部分，後面的隊伍分為兩部分，記住，每個人最多只需要做一次。

快速排序經常出現在面試題中，這是一個真正實用的排序方法。

代碼：

希爾排序

時間複雜度 $O(n^{2})$ ，空間複雜度 $O(1)$

應用場景：你從小就被韓信點兵的故事深深影響著，如今你也陞官為營長，管理者眾多士兵。當你學完了希爾排序後，你發現兩者竟有異曲同工之妙，於是你召集所有士兵，讓他們依次報數，報完數後你說，報到5的倍數的人出列，你讓他們用你教他們的插入排序的方法排好序，然後又說，報到3的倍數的人出列，你再讓他們用你叫他們的插入排序的方法排好序，最後你說，所有人用我教你的插入排序的方法排好序，你發現這三趟下來用的時間竟然比直接插入排序用時還短！但你百思不得其解。

代碼：

堆排序

時間複雜度 $O(nlogn)$ ，空間複雜度 $O(1)$

應用場景：

代碼：

代碼以後再上，文章包含於

彭瑤：C語言學習路線?

zhuanlan.zhihu.com
推薦閱讀：

※七本書籍帶你打下機器學習和數據科學的數學基礎
※序列化二叉樹
※新手如何學習演算法？演算法如何入門以及零基礎入門演算法應該學些什麼?學習路線是什麼
※凸優化筆記(4)Semi-Definite Programming簡介
※大六壬演算法講解

TAG:排序演算法 | 演算法 | 編程 |