Counting Sort 計數排序

在解決演算法問題時，我們常常會遇到排序問題，最簡單的解法我們通常會使用內建的 sort() 方法實作，不過排序之後這代表 Solution 的時間複雜度至少會大於 $O(nlogn)$ (根據語言、語法的不同，通常最常見的實作可能會是 Quick Sort)。

如果你遇到的演算法題目著重的就是排序法本身（就是要考排序，而不是排序只是解題過程中間的一步的話），有可能就代表會希望你能夠在時間上改善加快，而不是單純使用一個內建的 sort()，例如：面試官會要求你改善時間複雜度、或是平台送出 $O(nlogn)$ 的解法會導致 TLE。而要對 $O(nlogn)$ 的演算法進行改善，我們可以考慮 $O(n)$ 的排序法，而 Counting Sort 計數排序就是其中之一。

Counting Sort 是一種非比較排序法，不需要透過比較元素就能完成排序，而能夠從 $O(nlogn)$ 加快到 $O(n)$ 的關鍵，就是以空間換取時間的策略。想像一下，如果今天有一個超級長的陣列，裡面隨機放滿了 0, 1, 2, 3, 4 五個不同的整數，當我們要排序的時候，一個簡單的想法就是，如果我們知道陣列中，0 的個數有幾個、1 的個數有幾個、以此類推的話，我們是不是就很容易能夠做出排序完的結果了？如果你已經理解這個 idea，這就是 Counting Sort 的精神。

Example: 請從小到大排序 list = [ 3, 4, 1, 1, 0, 2, 0, 1, 3, 1]，其中 $0<=list[i]<=4$
Idea:

1. 計算出現個數
   • 有 2 個 0、有 4 個 1、有 1 個 2、有 2 個 3、有 1 個 4
2. 產生排序結果
   • 走過所有可能出現元素（從小到大依序為0~4），根據元素出現個數放入 list內
3. 已排序完成！

其中我們可以發現，要進行 Counting Sort 的話，有一個很大的先決條件，那就是我們必須知道要排序的元素的範圍，而這個範圍也不能太大，才能夠達到以空間換取時間的效果，而從實作層面來說，這個範圍通常會是整數或其他可數有限範圍（例如：英文字母 a-z, A-Z），反之如果要排序的範圍是 0~1 中的浮點數，就可能不太適合 Counting Sort，因為很難預先知道元素所有可能性。

最後我們一起看一下，將以上想法以 Python3 實作的程式碼吧！在實作時我們也將元素範圍放寬到 0~99：

• input: [ 3, 4, 1, 1, 0, 2, 0, 1, 3, 1]
• output: [0, 0, 1, 1, 1, 1, 2, 3, 3, 4]

Sample Code:

def countingSort(arr: list):
    counter = [0] * 100
    for element in arr:
        counter[element] += 1

    idx = 0
    for key in range(100):
        while counter[key]>0:
            arr[idx] = key
            counter[key] -= 1
            idx += 1
    return arr

arr = [ 3, 4, 1, 1, 0, 2, 0, 1, 3, 1]
print(countingSort(arr))