計數排序是需要假設輸入資料的排序之一，它假設輸入元素是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]; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/73349.html
標籤：C++
下一篇：JAVA工程師簡歷模板