計數排序 算法

算法思路

1. 統計待排序數列中每個數字出現的次數
2. 入資料結構的過程其實就是排序的過程
3. 最後再按照統計結果覆寫原序列就行了

算法實作

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的則将其重新放入數組之中
    count[ret] --;
  }
}      

算法分析