吳軍老師的《得到》專欄谷歌方法論中毒返，有幾節(jié)課是講排序算法的。排序舷手，作為算法里面最為基礎(chǔ)的一種拧簸，看似簡單卻非常值得深入研究，并且在研究算法的過程中也能感悟出一些平時做人做事的道理男窟。上周我寫過一篇文章盆赤，算是復(fù)盤學(xué)習(xí)到的最基本的兩種排序算法知識，從最基本的選擇排序和插入排序算法的對比中了解到蝎宇，要想提高做事的效率弟劲，就要盡量少做事情，盡量把握現(xiàn)有條件姥芥，把時間和精力花在最值得投入的地方兔乞。

在這周，我學(xué)習(xí)了更為高級的排序算法，歸并排序和快速排序庸追，這兩種算法在理論上的時間復(fù)雜度為O(nlogn)霍骄，通過數(shù)學(xué)證明能夠證明這種復(fù)雜度是無序數(shù)組排序時間復(fù)雜度最優(yōu)的極限。但在實際應(yīng)用中淡溯，這兩種算法又有自己的問題读整。人們會根據(jù)實際情況對其進行各種適用于特定場合的特殊優(yōu)化處理。通過學(xué)習(xí)咱娶，我除了更加深入了解這兩種排序算法之外米间，更有這樣的感觸：

1、如果能夠根據(jù)實際情況膘侮，對不同的事劃分出不同的優(yōu)先級屈糊，分類進行處理，然后再歸總琼了，效率要比同等對待高得多逻锐。也許這就是從計算機算法的角度詮釋了《高效能人士的七個習(xí)慣》中“要事優(yōu)先”的原理。

2雕薪、不同的情況下昧诱，沒有哪種方法是放之四海而皆準的。沒有高端方法和低端方法之分所袁，實踐是檢驗真理的唯一標(biāo)準盏档，能高效解決問題的就是好方法。

歸并排序算法：自頂向下分解問題燥爷，自底向上合并答案

首先通俗介紹一下歸并算法的原理妆丘。歸并算法本質(zhì)上是不斷將數(shù)組二分的過程。假設(shè)待排序數(shù)組的個數(shù)為8局劲，第一次將數(shù)組從中間分為兩段亡脸，每段長度為4（如果數(shù)組長度為奇數(shù)屯仗，那么就分成長度相差1的兩段）；第二次將兩段長度為4的數(shù)組再次二分联逻；第三次將四段長度為2的數(shù)組再次2分毅戈，數(shù)組退化成為8段長度為1的數(shù)組苹丸。請注意，當(dāng)數(shù)組長度為1的時候苇经，它就退化成一個不需要排序的數(shù)組了赘理。接下來，關(guān)鍵的是做“歸并”操作扇单，即先把2個已經(jīng)有序的元素長度為1的“歸并”成長度為2的有序數(shù)組商模。接下來，再把兩段長度為2的有序數(shù)組“歸并”成長度為4的有序數(shù)組。最終施流，再把兩段長度為4的有序數(shù)組“歸并”成最終有序的數(shù)組响疚。因此“歸并排序”本質(zhì)上就是自頂向下分解問題，自底向上合并答案瞪醋。

那么如何把兩段已經(jīng)有序的數(shù)組A和B歸并成一大段有序的數(shù)組呢忿晕？其實也很簡單。這里银受，我們需要首先申請一段長度為兩小段待歸并數(shù)組長度之和的內(nèi)存空間C践盼。首先，比較比較A和B的第一個元素宾巍，誰更小咕幻，就把這個元素拷貝到內(nèi)存空間的第一個。假設(shè)是A的第一個元素更小蜀漆，那么就把A的第一個元素拷貝過去谅河，接下來比較A的第二個元素和B的第一個元素，依次類推确丢。如果A先遍歷完绷耍，即A的元素已經(jīng)全部拷貝到新數(shù)組C中，那么接下來鲜侥，就把B中剩下的元素按B中原封不動的順序拷貝到C中（A褂始、B已經(jīng)有序保證了這樣操作后，C一定是有序的）描函。

最后崎苗，來考慮一下“歸并排序”的時間復(fù)雜度。首先舀寓，上一段介紹的“歸并”過程是一個O(n)復(fù)雜度的操作胆数，因為只需要完成一次遍歷A和B。而層層細分過程互墓，復(fù)雜度是O(logn)（長度為n必尼，求能被多少次二分，因此復(fù)雜度是2為底篡撵，n的對數(shù)）判莉。所以總體上的時間復(fù)雜度為O(nlogn)。（數(shù)學(xué)上的證明可以證明這個復(fù)雜度是排序算法的理論最優(yōu)）

“歸并排序”的特點是時間復(fù)雜度很“穩(wěn)定”育谬，無論原始數(shù)組是“完全順序”的還是“完全逆序”的券盅，完成排序的時間幾乎是相同的。因為都是反復(fù)從數(shù)組自頂向下二分膛檀，然后從底向上“歸并”锰镀。這樣就導(dǎo)致了當(dāng)數(shù)組元素很少或者只有很少數(shù)據(jù)是逆序的時候娘侍，它所化的時間還比不上之前所提到過的“插入排序”（接近完全順序的情況下插入排序的時間復(fù)雜度接近O(n)）。這就說明了數(shù)學(xué)上看似厲害的高級算法在某些場景會“水土不服”互站。

那么如何解決這個問題呢私蕾？一個明顯的改善就是我們其實不需要一直將數(shù)組二分到底。當(dāng)二分到一定程度胡桃，子數(shù)組長度已經(jīng)很短的時候踩叭，就可以考慮用簡單的插入排序了（當(dāng)長度很短時，實際情況中數(shù)組中逆序元素個數(shù)應(yīng)該很少）翠胰。實際情況中容贝，這種“歸并加插入”的算法能顯著提高效率。實踐是檢驗真理的唯一標(biāo)準之景，能高效解決問題的就是好方法斤富。

快速排序算法：將數(shù)組元素分成幾類，區(qū)別對待锻狗，最后合并答案

快速排序的思想是在數(shù)組中隨機選擇一個“排頭兵”满力。然后把數(shù)組分成三部分，把小于這個“排頭兵” 的放在最左側(cè)轻纪，把“排頭兵”放在中間油额，把等于“排頭兵”的數(shù)放中間，把大于“排頭兵”的數(shù)放右邊刻帚，然后再對小于和大于“排頭兵”的兩段數(shù)組進行同樣的操作潦嘶，直到最后把整段數(shù)組排序完畢。

這種把一個復(fù)雜問題先按一定標(biāo)準劃分崇众，再分而治之的思想在解決問題的時候非常有效掂僵。在實際測試中快速排序方法的所用的時間甚至能超過歸并排序，而且快速排序方法不需要為“歸并”而開辟額外的空間顷歌，因此比歸并排序來說能節(jié)省空間锰蓬。根據(jù)實際情況，優(yōu)化“排頭兵”的選擇眯漩，則能夠進一步提高效率互妓。在工程應(yīng)用中，快速排序仍然是使用的最為廣泛的排序算法坤塞。

吳軍老師對快速排序算法有自己獨特的感悟：如果我們講求絕對的公平，對每一個人澈蚌，每一件事都完全平等對待摹芙，那么效率就不可能做得很高。只有允許區(qū)別對待宛瞄，分類處理浮禾，才能做到最整體效率提升最大交胚。就像一所學(xué)校，想要提高整體水平盈电，必須對不同水平的學(xué)生進行“分班”蝴簇，因材施教。而我們?nèi)粘Ｉ钪袑Υ考煌氖虑榇抑悖残枰凑找欢ㄒ?guī)則進行分類熬词，比較重要的事情放在一起，很不重要的事情放在一起吸重，這樣才有利于高效處理事情互拾。

計算機算法，看上去是“冷冰冰”的邏輯推理和代碼嚎幸，但實際上也蘊含著不少哲理在里面颜矿。總的原則還是想要提高效率，就得少做事情嫉晶。根據(jù)事情不同的優(yōu)先級骑疆，分輕重緩急進行處理，分而治之替废，能夠顯著提高效率箍铭。同時，還需要根據(jù)實際情況進行變通舶担，高級的方法不代表任何情境下都能取得最好的效果坡疼。實踐是檢驗真理的唯一標(biāo)準。