CountingSort（計數排序）原理及C++代碼實現

計數排序是需要假設輸入數據的排序之一，它假設輸入元素是0到k區間內的一個整數，其中k為某個整數。當k=O(n)時，計數排序的時間複雜度為θ（n）。

因為不是通過比較來排序，所以它的時間複雜度可以達到θ（nlgn）以下。

計數排序是穩定的排序之一。

代碼如下：（僅供參考）

//計數排序期望輸入數據都是小區間內的整數
void CountingSort(int * const begin, int * const end) {
    vector<int> temp(10000); //假設輸入值小於10000
    vector<int> out(end - begin);

    for (int i = 0; i < end - begin; ++i)
        ++temp[*(begin + i)];
    for (int i = 1; i < 10000; ++i)
        temp[i] += temp[i-1];
    for (int i = end - begin - 1; i >= 0; --i) {
        out[temp[*(begin + i)] - 1] = *(begin + i);
        --temp[*(begin + i)];
    }
    for (int i = 0; i < end - begin; ++i)
        *(begin + i) = out[i];
}