你是大學圖書館的管理員。

正在享受午後的閒暇時光。

這時候，突然送來了1280 本書！

這些書被排成一行，

但是毫無規律。

剛好，自動分類系統又發生故障。

更糟糕的是，明天就要開學了；

也就是說明天一大早，

學生們就會湧入圖書館借書。

如何才能把所有書籍
及時整理好？

第一種方法：你可以從
排在最前面的兩本書開始，

如果這兩本書的順序正確，
那麼不做任何變動；

否則，互相交換這兩本書的位置。

接著再看第二本書和第三本書，

不斷重複上述過程，

一直到書列的末端為止。

在過程中，你可能就會碰到
應該排在最後的那一本書，

你會持續將這本書和後面的書交換，

將它不斷往後移動，
一直到最後面的位置。

然後再從頭開始，

不斷重複上述的步驟，
將倒數第二本書歸位，

一直持續到所有的書
都放在正確的位置為止。

這種整理的方法
叫做「氣泡排序法」。

原理很簡單，但過程很緩慢。

在第一輪過程就需要進行
1279 次的比較；

第二輪要比較 1278 次，
以此類推……

所以總共要比較 818,560 次。

如果比較一次需要 1 秒，

那麼你需要花費 9.5 天才能完成工作。

第二種方法是先將前面兩本書排好，

然後將第三本書
與位於第二位的書進行比較。

如果第三本書應該放在第二本之前，
則互相交換它們的位置，

然後再將這本書
與排在第一位的書比較，

如果有需要，就再交換位置。

現在，你已經成功安排好了前三本書，

接著每次將一本書
加入之前安排好的隊列中，

將新書與前一本作比較，
如果需要，交換它們的位置，

一直到這本新書被安置到
隊列中的正確位置。

這種方法叫做「插入排序法」。

與氣泡排序法不同，

它通常不需要比較
所有相鄰的兩本書。

平均來說，每本書
需要進行比較的次數

僅有氣泡排序法的一半。

這種方法總共需要比較
409,280 次，

大約需要 5 天時間。

然而，你需要比較的次數還是太多。

更好的辦法是，

首先，隨機選取一本書，
我們稱之為「分割點」；

將其他的每一本書
與分割點作比較，

然後根據分割點，
將這一排書分成兩部分，

將所有應該在分割點
之前的書放在左邊，

在分割點之後的書放在右邊，

這樣你就節省了大把時間，

因為不用再將分割點左半邊的書

與右邊的書進行比較。

現在，我們只關注分割點左邊的書，

你可以再一次隨機選一本書
作為新的分割點，

然後將其他的書分配在
新的分割點左右兩邊。

你可以繼續建立這種「子分割點，」

一直到分出了許多小型分支，

每一個分支中，
可以用其他更快的排序法，

例如插入排序法。

每一輪分割大約需要
進行 1280 次比較，

如果你的分割點分佈的非常均勻，

整排書分為 128 個分支，
每個分支 10 本書，

這樣大約需要七輪分割，
也就是 8960 秒。

每個分支當中，
大約需要再花 22 秒進行排序。

總體上來說，

這種稱為「快速排序法」的方法，

能將所有的書
在三個半小時內排列整齊。

但是這有個陷阱。

如果你的分割點非常偏向某一端，

就無法節省時間。

幸運的是，這種情況幾乎不會發生。

這就是為什麼快速分類法

在程式設計中
是最有效率的排序法之一。

例如在購物網站上，
將商品依照價格排序；

或是列出某個地點附近的加油站，

然後根據距離來排序。

在這個排書的例子中，
快速排序法幫你節省了許多時間。

真是多麼驚險刺激的一天啊！