上次我們介紹了好的算法和壞的算法區別有多大。那麼你可能會問，世界上已知的最好的算法是什麼呢，在評判“最好”之前，我們還是要加一些限制條件， 比如是一般清況下最好，還是惡劣的清況下最好。

 

講回到排序這件事，目前世界上遇常清況下最好的算法是一種叫做快速排序 ( Quicksort ）的算法，他是由英國計算機科學家托尼霍爾（ Tony Hoare）於1959年想到的，1961年發表的，這個算法也成了今天世界計算機產業中使用最多的排序算法，霍爾因此獲得了爵士頭銜， 也成為第一個獲得這種頭銜的科學家。那麼快速排序為什麼決呢？原因很簡單，它還是強調少做事清，其原理大致是這樣的：

 

首先，對於一大堆無序的數字，從中隨機挑選一個，比如是53，這個被隨機選上的數字被稱為樞值，接下來，將所有要排序的數字分成兩部分，第一部分是大於等於樞值 53 的，第二部分是小於樞值 53 的。在第一步完成後，一大堆無序的數字就變得稍微有序一點了。

 

第二步，從上面得到的兩堆數字，分別採用第一步的方法各自再找一個樞值。對於第一堆，由於所有的數字都比 53 大， 至少也等於 53，因此，第二次隨機挑選的樞值肯定是一個大於53的數字，比如 79；類似地，對於第二堆，由於所有的數字都小於53，因此第二次隨機挑選的樞值肯定小於它，比如4。接下來，再把兩堆數字各自分成大於等於相應樞值的數字序列， 以及小於樞值的數字序列。這樣做下來， 原來的一大堆數就變成了四小堆，它們分別是小於 4 的數字，介於 4 到 53 之間的，介於 53 到 79 之間的，以及大於或等於 79 的。

 

再接下來，用同樣的方法，四堆變八堆，八堆變十六堆，很陝所有的數字就排好序了。

 

這種算法通常清況下複雜度也是 N 乘以 log (N)，和昨天介紹的歸併排序相同。根據計算機科學的標準，它們同樣好，不過在工程上，快速排序算法一般清況下比歸併排序快兩倍，因此在工程上還是有意義的。這也是為什麼很多人用它的原因。至於為什麼決速排序能夠更陝一些呢？這可以在計算機科學上證明，不過為了方便理解，我打一個比方你就明白了。

 

假如有一個學區，裡面有 20,000 名高中學生，如果讓大家到一個超級大的學校上大課，再從中挑出學生中的尖子，效率一定高不了。這就相當於是昨天一開始講的冒泡排序，每一個人都要和所有人去比。如果我們把 2 萬人放到 10 所學校中， 每所學校只有兩千人，從各個學校先各自挑出學習尖子，再彼此進行比較，這就有效率得多了。這就是昨天說的歸併排序原理。

 

如果我們先劃出幾個分數線，根據個人成績的高低把 20,000 個學生分到 10 所學校去，第一所學校裡的學生成績最好，第十所最差，再找出學習尖子，那就容易了，工作量最小，這就是快速排序的原理，也是決速排序比昨天講的歸併排序快的原因。

 

其實，計算機算法和組織的管理，乃至社會的管理，在道理上有相遇性，想要提高效率就是要少做事倩。一個社會的管理，要想效率高，最簡單的辦法就是對每一個人作一些區分，而效率最低的辦法就是刻意追求所有人一律平等，不作區分。可以想像，當一個學校的學生水平都比較接近，老師教起來就容易，因此按照成績對學生作一個初步的劃分是有道理的，特別是在資源不足的清況下。反之，如果一個學校的學生從100分的到0分的都有，那麼老師教起來就困難了，如果想達到前面同樣的效果，就必須多投入資源。

 

從對比快速排序和歸併排序大約三倍的效率之差，我還得到一個啟發，那就是為什麼美國私營公司的效率會比政府高很多。美國的政府和社會要講究民主和平等，但是美國的公司裡從來不講這一套， 公司裡的大事從來不會和每一個員工商量，行政的層級就如同陝速排序事先劃定的樞值，有了三六九等，公司才有效率可言。

 

因此，當一個年輕的員工新入職後， 處於最低的層級時，不要指望公司的政策是照顧底層的員工，因為那樣的組織沒有效率，沒有效率的組織在競爭中是要死掉的，當一個公司死掉後，任何理想都成為了泡影。所以，每個底層員工所思考的事情，是如何進入更高的層級，這也是我從來不強調什麼底層思維的原因，畢竟大家將來是會不斷上升的，必須具有高層思維。底層思維，或者心靈雞湯，無異於是一種毒藥。如果你還在慶幸自己進入了一個最底層員工的工資和總經理差不多的單位時，趁著年輕趕陝離開，因為這樣的公司是要死掉的。

 

我在今天一開始講，決速排序是通常清況下最好的算法，但是，在極端的清況下，它的複雜度是 N 平方，和冒泡排序一樣糟糕。而歸併排序，即使在最壞的清況下，也能保證 N 乘以 log(N）的複雜度， 當然工程師們會想一些方法防止這種糟糕清況的發生。從這個例子可以看出，世界上沒有絕對的好，常常有一得便有一失。

 

最後大家可能還會有一個問題，隨著科技的進一步進步，有沒有可能發明一種比快速排序更好的算法？從科學上講，答案是否定的。因為從數學上可以證明 N 個任意隨機數的排序，複雜度不可能比 N 乘以 log(N）更低，這是數學給出的極限， 或者邊界，因此有點頭腦的人都知道別在這方面瞎費工夫。這也是我一直強調要在邊界內做事清的原因。

 

我在騰訊面試工程師時，曾經遇到過一個學習計算機科學的學生，總是不相信排序算法的速度是有極限的，我給他看數學上的證明，他因為數學基礎有限看不明白，於是我在想，這個人和痴迷永動機的人沒有什麼區別，沒有救了。花時間培訓這樣的人是瞎費工夫，最好的辦法就是像芒格說的那樣，將那種人排除在組織之外。

 

上面就是我從決速排序算法中屠出的生活裡的思維方式，希望對你有所啟發。

 

來源：《吳軍-快速排序： 要想提高效率就要少做事情》