计数排序 算法

算法思路

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] --;
  }
}      

算法分析