算法思路

1. 統(tǒng)計待排序數(shù)列中每個數(shù)字出現(xiàn)的次數(shù)
2. 入數(shù)據(jù)結構的過程其實就是排序的過程
3. 最后再按照統(tǒng)計結果覆蓋原序列就行了

PS: 前提條件是知道排序元素的范圍

算法實現(xiàn)

void count(vector<int> &arr, int range) {vector<int> count(range+1,0);for (int i = 0;i < arr.size(); ++i) { //一次遍歷，用hash記錄元素count[arr[i]] ++;}int ret = 0;for (int i = 0;i < arr.size(); ++i) {while(count[ret] == 0) ret ++;arr[i] = ret;//從小到大，訪問到hash不為0的則將其重新放入數(shù)組之中count[ret] --;}
}

算法分析

時間復雜度: O(n+k)，k為元素上限，接近O(n)，針對元素密集型的數(shù)組則排序優(yōu)勢較大。
空間復雜度: O(k)。

總結

以上是生活随笔為你收集整理的计数排序 算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。