當輸入的元素是 n 個 0 到 k 之間的整數時，它的運行時間是 Θ(n + k)。計數排序不是比較排序，排序的速度快于任何比較排序算法。

由于用來計數的數組B的長度取決于待排序數組中數據的范圍（等于待排序數組的最大值與最小值的差加上1），這使得計數排序對于數據范圍很大的數組，需要大量內存。計數排序是用來排序0到100之間的數字的最好的算法，但是它不適合按字母順序排序人名。但是，計數排序可以用在基數排序中的算法來排序數據范圍很大的數組。

測試代碼：

#include <iostream>
using namespace std;void print(int a[], int sz) 
{for (int i = 0; i < sz; i++) cout << a[i] << " ";cout << endl;
}void CountingSort(int arr[], int sz) 
{int i, j, k;int idx = 0;int min, max;min = max = arr[0];for (i = 1; i < sz; i++) {min = (arr[i] < min) ? arr[i] : min;max = (arr[i] > max) ? arr[i] : max;}k = max - min + 1;int *B = new int[k];for(i = 0; i < k; i++)B[i] = 0;for(i = 0; i < sz; i++) B[arr[i] - min]++;  //記錄該元素的個數for(i = min; i <= max; i++)for(j = 0; j < B[i - min]; j++) arr[idx++] = i;print(arr, sz);delete[] B;
}int main()
{int a[] = { 5,9,3,9,10,9,2,4,13,10 };const size_t sz = sizeof(a) / sizeof(a[0]);print(a, sz);cout << "----------------------\n";CountingSort(a, sz);
}

參考資料

1.??漫畫：什么是計數排序？?