概述

計數排序是一個非基於比較的排序算法，該算法於1954年由 Harold H. Seward 提出。它的優勢在於在對一定範圍內的整數排序時，它的複雜度為Ο(n+k)(其中k是整數的範圍)，快於任何比較排序算法。 當然這是一種犧牲空間換取時間的做法，而且當O(k)>O(n*log(n))的時候其效率反而不如基於比較的排序(基於比較的排序的時間複雜度在理論上的下限是O(n*log(n)), 如歸併排序，堆排序)。

算法思想

計數排序對輸入的數據有附加的限制條件:

1、輸入的線性表的元素屬於有限偏序集S;

2、設輸入的線性表的長度為n，|S|=k(表示集合S中元素的總數目為k)，則k=O(n)。

在這兩個條件下，計數排序的複雜性為O(n)。

計數排序的基本思想是對於給定的輸入序列中的每一個元素x，確定該序列中值小於x的元素的個數(此處並非比較各元素的大小，而是通過對元素值的計數和計數值的累加來確定)。一旦有了這個信息，就可以將x直接存放到最終的輸出序列的正確位置上。例如，如果輸入序列中只有17個元素的值小於x的值，則x可以直接存放在輸出序列的第18個位置上。當然，如果有多個元素具有相同的值時，我們不能將這些元素放在輸出序列的同一個位置上，因此，上述方案還要作適當的修改。

算法步驟

1. 找出待排序的數組中最大和最小的元素
2. 統計數組中每個值為i的元素出現的次數，存入數組C的第i項
3. 對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）
4. 反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1

示例

輸入{3, 4, 3, 2, 1}，最大是4，數組長度是5。

建立計數數組{0, 0, 0, 0}。

遍歷輸入數組：

{3, 4, 3, 2, 1} -> {0, 0, 1, 0}

{3, 4, 3, 2, 1} -> {0, 0, 1, 1}

{3, 4, 3, 2, 1} -> {0, 0, 2, 1}

{3, 4, 3, 2, 1} -> {0, 1, 2, 1}

{3, 4, 3, 2, 1} -> {1, 1, 2, 1}

計數數組現在是{1, 1, 2, 1}，我們現在把它寫回到輸入數組裡：

{0, 1, 2, 1} -> {

{o, o, 2, 1} -> {1, 2, 3, 2, 1}

{o, o, 1, 1} -> {1, 2, 3, 2, 1}

{o, o, o, 1} -> {1, 2, 3, 3, 1}

{o, o, o, o} -> {1, 2, 3, 3, 4}

這樣就排好序了。

• 時間：O(n + k)，n是輸入數組長度，k是最大的數的大小。
• 空間：O(n + k)，n是輸入數組長度，k是最大的數的大小。

代碼實現：

閱讀更多 咱小二 的文章

關鍵字: 算法 排序 技術