上一章節我們分析了comparison sort的極限在哪，這章節會來討論不使用comparison來進行sort有哪些方法。

首先老師介紹了一個奇妙的想法，叫做sleep sort：

讓電腦以秒為單位來睡，當睡的秒數遇到array中的數字時，就print出來，等睡到最大的元素後就完成sort了。

以此想法為根基，假若我們不是以時間作為順序，而是空間呢？這就是counting sort：

以上面的案例來講，總共有0~11，先創出空白的array，再根據key的大小一一填入，就完成sort了。當然現實中不可能遇到這麼工整的array讓你sort，所以接著會探討當key不是這麼工整的時候，counting sort是否也能應對？

以下範例使用撲克牌的花色作為key，並有一個預設條件的順序（梅花，黑桃，紅心，方塊）

根據花色的個數，我們可以定義出每個花色的起始index應該是多少（左邊數來第三張表），然後在每次歸類到該花色時，表中的index就加一：

如此類推，就可以完成counting sort。

那counting sort的runtime是什麼呢：

Θ(N + R)，其中N是array的元素總數，R是key的種類數。

介紹完counting sort，接著討論更複雜的情況。剛剛我們的key都只有單一的分類，那假若像string怎麼辦呢？其實也不是太大的問題，就只是key每多一個單位，我們就多sort一遍罷了，所以我們可以把string想像成複數個花色這樣，抑或是一個字母與數字組成的代碼，其實沒什麼太大的不同：

而要針對複數key來sort，最安全的做法就是先從key的最右邊開始sort，依序再往左來看key是什麼來sort，這樣的做法稱為LSD(Least Significant Digit)，從最不重要的digit開始sort：

而LSD的runtime會是Θ(WN + WR)，W就是key的寬度。

介紹完LSD，就可以接著思考，那假若我們不從最右邊sort，而直接從最左邊呢？可行嗎？

看來是不可行的了，因為我們先sort好的最左邊digit很可能會被接下來的digit打亂應有的順序。必須換另一種思維：

如上，當我們分完第一個元素後，就把它當成一開始counting sort的分類，在接著分第二個元素，以此類推後，就可以順利sort完成。

MSD的Runtime，可以發現最好的狀況可以更好，但最差的情況會跟LSD一樣。

以下是目前為止介紹過的sort總結：

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License