圖書館劉大媽除了要幫我找對象，還教我排序演算法

在圖書館偶遇

快速排序演算法

1一次關於排序的偶遇

今天，在圖書館發生了一件事。

圖書館書架

新來的志願者小王被安排將歸還的書整理回書架，初次被委派工作的小王瞬間充滿熱情。然而。。。

面對地上一大堆書籍，小王瞬間懵了，手足無措，望書興嘆。

此時老圖書館管理員劉大媽向小王款款走來：小夥子，今年幾歲了，有沒有女朋友，大媽幫你介紹一個，你喜歡什麼類型。。。

小王瞬間再次懵了：大媽，現在是科普頻道，不是《非誠勿擾》。。。

劉大媽此時才緩過神來：像你這樣整理，不知道要整理到何年何月，一般呢，你就這麼排書，隨便在這堆書當中抽出一本書，把比它大號的放在左邊，比它小號的書放右邊，完了以後，你們繼續在每一堆繼續這樣排，這樣排得快。

小王在旁邊一聽，感覺怎麼這麼熟悉：我的天，竟然連圖書館管理員都學排序演算法吧！這圖書館有...

要知道快速排序演算法是人類當今最最常用的，計算效率方面最優秀的排序演算法！管理員劉大媽竟然深諳此道，把這個演算法用到排書上。

快速排序的過程示

快速排序演算法（Quick Sort），顧名思義他的排序速度很快。快速排序演算法在1959年由英國科學家托尼·霍爾（Tony Hoare）發明。

2快速排序怎麼來的？

1959年，托尼·霍爾當時在莫斯科國立大學作為訪問學生，參與到莫斯科國家物理實驗室的一個機器翻譯（Machine Translation）項目。其中有一個技術點是，需要對俄語句子進行排序。

霍爾首先想到的是插入排序，可是霍爾嫌棄它的效率太低了。為此，霍爾詳盡各種辦法，終於想到了一個更好的排序思路（快速排序的雛形），並且寫出了代碼。原本準備開始大展拳腳之時，沒想到演算法中還存在一些不能被排序的部分，無奈之下，霍爾只能選擇擱置了。

博士畢業回到英國以後，霍爾在埃利奧特兄弟公司（Elliott Brothers, Ltd.）任職。

有一天，霍爾的老闆讓他用希爾排序（Shellsort）的代碼對一份材料進行處理。霍爾告訴他的老闆：

BOSS，我覺得希爾排序還是慢了，我有一個新的演算法，效率可以更快，你信不信？

霍爾的老闆一聽，這怎麼可能，還有比希爾排序更快的演算法。「小兄弟，我也是技術出身，你可別逗我，怎麼會有比希爾排序更快的演算法。行，我賭六便士，賭你做不出來。」

霍爾自然接下挑戰，這一次霍爾很快就把新演算法寫出來了，從時間複雜度上完勝希爾排序。

霍爾的老闆雖然輸掉了賭注，但是非常賞識眼前這位年輕人。後來霍爾參加了由Dijkstra（傳送門）舉辦的ALGOL 60培訓班，了解到ALGOL 60具備實現遞歸的能力，促使他設計了ALGOL 60的一個商用版本。

ALGOL ，為演算法語言（ALGOrithmic Language）的縮寫，是計算機發展史上首批產生的高級程式語言家族。

這個版本在執行效率和可靠性上都在當時ALGOL 60的各個版本中首屈一指，不僅受到了老闆的重視，榮升公司的首席工程師，而且受到了國際學術界的重視。由於在編程語言定義和設計方面的基礎性貢獻，霍爾獲得了1980年的圖靈獎。

中國版的ALGOL 60的教材。ALGOL 60作為人類最早期的高級語言，擁有世界範圍內的影響力。

3什麼是快速排序？

快速排序是目前處理大數據最快的排序演算法之一。快速排序的思路非常清晰，簡單地說，就是對要排序的數，隨意以一個基準分成兩部分，其中一部分比另一部分要小。然後再繼續分別對這兩部分進行排序。

快速排序具體的演算法步驟如下：

Step 1：基準選取：從數列中選取一個元素，稱為基準（pivot）。

Step 2：數列分割：重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面。最終該基準就處於數列的中間位置。這個是分割操作（partition）。

Step 3：遞歸執行：對小於基準值元素的子數列和大於基準值元素的子數列分別執行快速排序。

舉個例子，我們嘗試用快速排序對這個數列進行升序排列：

Step 1：首先，需要找一個基準，我們就找第一個數字6，作為基準。

Step 2：我們要達到一個目標，用基準將數列分割成兩部分，得到以下這種排列：

其中，6左邊的所有數字不大於6，6右邊的所有數字不小於6。為了實現這個效果，需在數列內部執行元素的移位。

首先，設置兩個變數，分別是變數i和變數j。變數i和變數j起始位置分別是1和10，我們可以假想他們是兩列馬車，分別往對面方向開。

馬車i的任務是一步步往右走，如果遇到大於基準6的數字就停下來。馬車j的任務則相反，一步步往左走，如果遇到小於基準6的數字就停下來。後來，馬車i停在了7上，馬車j停在了5上，這個時候我們對調7和5的位置。

交換位置以後的結果如下：

交換以後，馬車i繼續往右走，馬車j繼續往左走，馬車i停在了9上，馬車j停在了4上。此時再次進行交換。

第2次交換位置以後的結果如下：

交換以後，馬車i繼續往右走，馬車j繼續往左走。假設馬車j先走，馬車j停在了3上，馬車i再走，走到3這裡與馬車j碰上停下來了，此時馬車i和馬車j的探測任務完成了。我們將基準數6與3進行交換。

第3次交換位置以後的結果如下：

這樣，對於數列的分割就完成了。

Step 3：繼續對分割出來的兩部分數列，繼續進行快速排序的遞歸操作。

執行完這3步以後，快速排序的操作就完成了，序列變成有序序列。

4快速排序的時間複雜度

同一問題，比如以排序為例，同樣的排序問題，可以用不同的演算法來解決。而演算法設計的優劣將影響到演算法的工作效率，那麼如何比較不同演算法之間的工作效率呢？

演算法的時間複雜度，解決了這個效率比較的問題。時間複雜度是一個函數，它定性描述了演算法的運行時間，通常用大O符號來表述。

常見的演算法時間複雜度由小到大依次為：

常數階Ο(1)＜對數階Ο(logn)＜線性階Ο(n)＜線性對數階Ο(nlogn)＜平方Ο(n²)＜立方階Ο(n³)＜…＜指數階Ο(2ⁿ)＜階乘階Ο(n!)。

科學家們發明了大量的排序演算法，我們可以總結幾種常用的排序演算法的時間複雜度在時間複雜度上的表現：

冒泡排序的時間複雜度為Ο(n²)，表示隨著數據規模n的增加，所耗費的時間呈n²速度增長。而快速排序的時間複雜度為Ο(nlogn)，比Ο(n²)降低了一個數量級，具有重大的理論意義與實際價值。（小智寫過歸併演算法和堆排序的相關介紹）

這就是研究排序演算法的原因所在。如果排序演算法仍然沿用O(n²)數量級的演算法，尤其是在數據量日益增加的今天，所耗費的計算資源將大大增加，稍微大一點規模的數據將無法處理。

本文系網易新聞·網易號「各有態度」特色內容

本文部分資料來源於網路

轉載請在公眾號中，回復「轉載」

-----這裡是數學思維的聚集地------

「超級數學建模」（微信號supermodeling），每天學一點小知識，輕鬆了解各種思維，做個好玩的理性派。50萬數學精英都在關注！

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！