文章首發(fā)：微信公眾號【九粽】
大噶好！轉(zhuǎn)眼間我們上班的上班，上學(xué)的上學(xué)，相信已經(jīng)有一陣子了。
面對工作中要處理的花花綠綠的數(shù)字，我們最常用的操作可能就是——花里胡哨看不出來什么，要不先排個序吧。
?
咔咔一點(diǎn)，數(shù)據(jù)排好了序，仿佛是等待你檢閱的士兵。
排序——自古以來就是非常實用的一個理清事物的方法。比如早操排隊會按高矮排序，史料記載會按時間排序，單詞查找會按字母排序，YB國會按沙雕程度排序（國王第一，其余全部并列第二）。
計算機(jī)世界也是一樣，對排序有著強(qiáng)烈的執(zhí)念。既然有了這個需求，下面就是怎么辦的問題了。
注意：閱讀本文不需要任何計算機(jī)知識，相反的，閱讀本文過后你會具備一些計算機(jī)常識。
現(xiàn)在，你前面站著一排小學(xué)生準(zhǔn)備做早操，首先需要你想辦法把他們從矮到高排成一列，下面的數(shù)字代表小學(xué)生的高度：
7，6，9，8，5，1 （不要在意“1是多高”這種細(xì)節(jié)）
為了彰顯我本人的聰明才智，排序后正確答案我現(xiàn)在就給出來，是1，5，6，7，8，9。
此刻我相信，家里有體育老師經(jīng)常給學(xué)生排隊的，在這個問題上應(yīng)該不輸給數(shù)學(xué)老師。一下子映入腦海的可能就有以下幾種方案。
方案一：你也許會說，這個簡單，我先一眼揪出那個最高的，然后把他直接放到最后面。再在剩下的里面揪出最高的，排在倒數(shù)第二個……依次類推。
這個方法非常直觀，并且有效。每次選擇出一個最高的，在計算機(jī)里面的名詞也很直白，就叫選擇排序。
問題來了，如果有1000個學(xué)生，一眼望不到頭。那么這是體育老師就要和數(shù)學(xué)老師合作了：體育老師從頭跑到尾，看當(dāng)前誰是最高的；數(shù)學(xué)老師站在隊尾，告訴體育老師他剛才已經(jīng)記到哪兒了。
【親愛的，我跑了一趟，這個最高！】
【么么噠，把這學(xué)生交給我吧，你去看看剩下的誰最高】
【親愛的，我又跑了一遍，現(xiàn)在這個最高！】
【么么噠，這是第二高的學(xué)生，你再去看看剩下的】
……
【親愛的，我又跑了一遍，現(xiàn)在排到哪兒了？】
【我這里有233個排過序的了，你再跑一遍看剩下誰最高】
……
最后排隊成不成功我不知道，但是體育老師估計是要累死了。
方案二：體育老師站了出來，mmp勞資不跑了！全體都有！我吹一聲哨子，每個人就跟前面的人比比個子，要是前面的人高，你就跟他換一換！
?（qū）一聲哨響，個子矮的人往前換了換；
又一聲哨響，個子矮的人又往前換了換；
……
最終，個子最矮的那個小朋友站在了隊伍最前面。
這個最矮的小朋友，每次前進(jìn)一位，就像小魚兒吐出的泡泡，Bububu的一點(diǎn)一點(diǎn)浮到了水面上（就是隊伍最前面）。這種自底而上的挪動過程，計算機(jī)算法的名字也很直白，叫冒泡算法。
問題又來了，如果有1000個小朋友等待排隊，這時候體育老師會怎么吹哨呢？
【?！——】過了一會兒，最矮的小朋友排到了第一個；
【?！——】又過了一會兒，第二矮的小朋友也浮到了隊伍前面，跟第一位比了比之后，排在了第二個。
……
【?！——】第299次哨響過后，前幾名的小朋友哭了：【老師，我們的位子早就固定了，別讓我們每次都比較了吧？】
【這可咋辦呢？……】這個問題涉及到了體育老師的知識盲區(qū)。
【親愛的我來幫你吧】關(guān)鍵時刻還是數(shù)學(xué)老師挺身而出，【你第一次吹哨，說明第一個小朋友就已經(jīng)排好了。這樣，跟剛才一樣，你每次吹完哨我都幫你數(shù)著，那前面的小朋友們就不用再比較了】
【親愛的你可真聰明！】體育老師眼角泛起了淚花。
【就一點(diǎn)小忙，不用感動到落淚……】
【不是感動，是我tm吹了1000次哨子，哨子犧牲了……】
方案三：得，這下體育老師哨子也沒了，還是得跑。不過我們似乎可以在方案一的基礎(chǔ)上改進(jìn)一下。
（別告訴你已經(jīng)忘記方案一是啥了……）
之前體育老師每次都要從頭到尾跑，找出最高的小朋友。
現(xiàn)在讓他省省勁兒：數(shù)學(xué)老師那兒不是已經(jīng)排好隊了嘛，體育老師提起一個沒排隊的小朋友走到數(shù)學(xué)老師的隊里。
從前往后走，邊走邊跟手上的小朋友比較。
找到合適的地方就把小朋友往那兒一放就行，不用往后走了。
搞事的那1000個小朋友又來了……
【親愛的，這是第一個小朋友，放你這兒?！?/p>
【這是第二個小朋友，讓我看看……你比第一個小同學(xué)高，你就排他后面吧】
【這是第三個小朋友，嗯…你比第一個高，但比剛才第二個矮，你就排中間吧…】
……
【這是第666個來排隊的小朋友，在排好隊的同學(xué)里…我瞅瞅…你比前100名高，但比101名矮，那你就排100的后面吧】
就這樣，雖然每次體育老師還是要跑來跑去，但是每次點(diǎn)到為止，不需要從頭跑到尾。這種每次提著小朋友插♂入到合適位置的方法，計算機(jī)語言同樣直白，就叫插入算法。
到這里為止，各位已經(jīng)明白了計算機(jī)三大簡單排序算法，可以給自己鼓個小掌以示鼓勵，或者點(diǎn)一頓燒烤作為獎勵。
不過這幾個方法的弊端也是顯而易見的：
（1）一定要數(shù)學(xué)老師和體育老師合作；
（2）體育老師總是累得要死要活。
如果把體育老師換成一個別的老師，可能光是跑來跑去就要耗費(fèi)不少時間，為了彰顯體育老師的特長，在計算機(jī)里，我們總得有個酷炫的名詞來衡量一個方法花了多少時間，它就叫?時間復(fù)雜度。
那上面幾個方法都花了多少時間呢？我們再把那1000個小朋友拉出來。
——首先，數(shù)學(xué)老師手里的學(xué)生一開始沒有，然后越來越多，每次增加一個已經(jīng)排好隊的學(xué)生。
——每當(dāng)數(shù)學(xué)老師手里增加一個排好隊的學(xué)生，就意味著這是體育老師跑遍了剩下的學(xué)生，為她找出來的。
——那這時間就是1000*1000 （四舍五入就是一個小目標(biāo)?。?/p>
——體育老師的這種舍己為人，無私奉獻(xiàn)的精神，我們稱之為?舔狗精神?白求恩精神。
——雖然體育老師后來改進(jìn)了，不用全都跑，但如果人數(shù)特別特別多，他節(jié)省的時間比起巨大的數(shù)據(jù)量，可以忽略不計。
——即，以上算法的時間復(fù)雜度都是n2。
還能不能給體育老師一點(diǎn)活路？……
直到1959年，有一個叫Shell 的人橫空出現(xiàn)，提出了一個劃時代的方案……
你是不是那個Shell？
