我們昨天的內容算是一個鋪墊，確立了評判計算機算法好壞的基礎和標準。今天我們以計算機科學中最常見的算法 — 排序算法為例，說說提高效率的本質。

 

排序是我們在生活中經常會遇到的事清。在學校裡老師會把一個年級的學生按照成績排序，或者按照中學所在的地域排序；做電商的人，可能需要把所銷售的各種商品按照收入或者交易量排序。排完序，我們有時就能看出很多規律，或者作進一步的處理了。

 

計算機最早的排序算法源於人的生活和經驗，這就如同最早的計算機下棋是模仿人，最早設計的飛行器是模仿鳥一樣。那麼我們人是怎麼排序的呢？如果只有三五個數字，我們可以掃一眼就排完了序。但如果到幾十個數字，這就有點麻煩了， 因為如果沒有一個必須嚴格遵守的流程， 排完序經常會有些小錯誤。我在中學時還沒有計算機，我們常常幫助老師統計同學們的期末考試成績，發現把一個班上五十個人的成績排序絲毫沒有錯誤，並不容易。後來我們發現比較可靠的辦法其實是下面兩種笨辦法：

 

方法一：第一次挑出成績最高的同學，第二次挑出成績次高的，如此重複， 肯定能完成成績的排序，一定不會錯。

 

方法二：先將成績單上第一個同學的名字和成績寫到旁邊一張白紙的中央，如果第二個同學成績比他高，就寫到第一個同學的上方，如果比他低，就寫到下方。等看到第三個同學的成績後，根據他的成績與前兩個同學成績的比較，插入到相應的位置。

 

比如他的成績正好在兩個同學之間，就在旁邊那張排序的紙上，把他的名字插入到前兩個人之間。當然，那張排序的紙要留夠空白，以方便插入後來同學的名字。

 

其實，早期的計算機科學家比我們也強不到哪裡去，他們提出的排序算法就是上面兩種。第一種算法被稱為冒泡排序， 因為每一次選出一個最好的，如同從水里冒出的氣泡。第二種被稱為插入排序，因為每一次要找到合適的位置插入。

 

接下來我們就用高德納的思想，分析一下上述算法的複雜度。第一種算法很容易估算，50個人中找出最大的要比較 49 次，第二大的要比較48次，以此類推，大約是1200多次，是50的平方的一半左右。

 

第二種算法的複雜度，也是和 50 的平方有關，這裡就不再分析了。如果我們把 50 擴展到任意一個整數 N，事實上使用上述排序的複雜度都是 N 平方左右。我們昨天講到，在衡量計算機算法複雜度時，科學家們不關心幾倍的差別，因此，在用數學公式表達複雜度的時候，高德納乾脆刪除了前面的常數因子，只保留後面的變量，他用了微積分中的一個概念一一大寫的 O 的概念，所有同等複雜度的算法，都被認為它們在大0的概念下是相等的。比如，上述冒泡排序算法的複雜度是 O ( N 平方），插入排序也是 O ( N平方），屬於同一個量級。此外，早期的計算機科學家還想出了其他的排序算法，複雜度都和它們差不多，在一個量級。

 

接下來怎麼提高計算機算法的效率呢，節省 20％ 的計算量是沒有意義的事清，就算省個三五倍也沒有意義，要省就乾脆多省一點，省它個成千上萬倍甚至更多。於是，全世界所有的算法專家經過了十多年，終於發現從經驗出發的排序速度漫的原因，就是做了無數的無用功。要提高效率，就需要讓計算機少做事情。

 

以冒泡排序為例，之所以慢，是因為每一次選出一個最大的數，都要和其它所有的數字相比，其實並不需要這麼麻煩， 要想提高效率，就要減少數據之間的相互比較。最早對冒泡排序的改進是一種叫做歸併排序的算法，它就利用了少做事清的思想，歸併排序的思想大致如下：

 

首先，科學家們發現，如果我們把全班同學分成兩組，分別排序，那麼從每一組中挑選出一個最大的，就能省去一半的相互比較時間。於是他們就先將整個班級一分為二，先分別進行排序，再把兩個排好序的組，合併成為一個有序的序列。相比排序，對有序的序列合併是很快的。歸併排序這個詞就是這麼來的。這樣做大約可以節省一半時間。當然，我們在前面也講過，節省一半時間意義不大，但是別著急，因為對一個班級分出來的兩個小組， 排序時也可以採用上述技巧。

 

第二步，就是對兩個組的排序。顯然我們不應該再用冒泡排序。聰明一點的人馬上會想到，既然能分成兩組，就能把每個小組再分為兩組，即分成四組，重複上面的算法，分別排序再合併。這樣就能省 3/4 的時間。

 

再接下來，四組可以分為八組，能省7/8的時間，八組可以分為十六組，時間就不斷省得越來越多。分到最後每個小組只剩下兩個人的時候，其實就不用排序了，只要比較一次大小即可。

 

這種方法其實可以理解為兩個過程， 先是自頂向下細分，再自底向上合併。那麼這種算法的複雜度等於多少呢？它相當於 N 乘以 log(N) , log(N）就是 N 的對數函數，大家不必在意 N 乘以 log (N）是什麼東西，只要記住它和 N 平方不一樣， 而且這個複雜度比前面的N平方小很多就行了。

 

為了便於你理解它小了多少，我們看看當 N 分別是100, 1萬，1百萬，1億時， 兩種算法的複雜度的清形：

 

第一種：即N平方，當N是100, 1 萬，1百萬，1億時，它對應1萬，1億，1 萬億，1億億

 

第二種：即N乘以log (N )，它對應700, 13萬，2000萬，23億。

 

你可以看出N比較大了以後，N 乘以log(N）比 N 平方要小很多，即 23 億和 1 億億的差別，相差大約400萬倍。400萬是什麼概念呢？大約是一支毛筆的長度和北京到上海距離的差別，或者是你和我兩個人的重量和航空母艦重量的差別。

 

這樣一對比，你就能感覺到為什麼計算機的算法是如此重要。算法沒有學好的人，寫出來的程序經常是不合格的，因為很容易就浪費掉成乾上萬倍的計算機資源。大家不要覺得一個億是什麼了不得的大數字，且不說騰訊或者阿里巴巴這樣公司的用戶數早就超過了一個億，即使你編寫一款遊戲，只要有人使用，幾天下來的日誌都有上億行，對一億個數排序，在計算機應用中是很常見的事清。

 

歸併排序算法相比之前的算法為什麼效率提高這麼多？因為它少做了很多並不需要做的比較。很多人問我，你為什麼效率這麼高？並不是我效率高，而是做事清比大家少。效率二產出／所做的事倩。人的產出是很難提高的，但是所做的事清是可以減少的。

 

我一直強調工程師水平差一級，貢獻可能就差出10倍，有人不服氣，說會差這麼大麼？從上面的一個例子大家可以看出，可能差得還不止十倍。很多人問，我想改行搞計算機，自己找兩本書看看是否就可以了？我的答案是不可以，在今天這樣一個人多粥少，人的技能普遍高出行業基本要求的時代，進入任何一個行業，都要有點專業精神，把自己當作科班出身來要求。在農耕文明時代，沒有力氣的人最不濟也能產生壯勞力 1/3 的生產力。在工業時代，靠手工一件件生產商品，可能效率能有機器的1%。但是到了智能時代，本事差一點，效果可能差幾百萬倍，幾億倍，專業和不專業就差得更遠了。

 

為什麼到了智能時代學習變得非常重要了呢？因為一些基本的方法和道理如果不學習，靠自己腦子苦思冥想可能需要十年甚至更多的時間，而學習加練習，可能只要一個月的時間就夠了。早期的計算機科學家因為受限於自己的生活環境，也想不出好的排序方法，今天比較常用的

 

不出好的排序方法，今天比較常用的排序算法快速排序（Quicksort)，是在計算機誕生後13年才出現的。這個算法，我下次花十分鐘時間，就可以給大家講清楚， 大家可以自己判斷，是應該學習，還是自己琢磨呢？

 

明天我們會談談決速排序，以及它背後的方法論。

 

來源：《吳軍-從計算機的算法，談談提高效率的本質》