算法导论：c++计数排序

今天药忘吃喽~ 2022-06-04 02:54 240阅读 0赞

区别于比较排序需要元素进行相互比较，计数排序仅仅通过元素个数确定它在排序结果中的位置。

这里写图片描述

这里写图片描述

代码实现

实在是不想用数组了，这次用方便易操作的vector代替。

  1. /*计数排序*/
  2. vector<int> counting_sort(vector<int> array,int k) //k表示数组中最大元素，output为输出
  3. {
  4.     vector<int> temp(k+1,0);//临时数组，存放个数
  5.     vector<int> output(array.size(), 0);//初始化输出
  6.     for (int i = 0; i < array.size(); i++) {
  7.         temp[array[i]] += 1;    //计算次数
  8.     }
  9.     for (int i = 1; i < temp.size(); i++)
  10.     {
  11.         temp[i] += temp[i - 1];     //计算个数
  12.     }
  13.     for (int i = array.size()-1; i >=0; i--)
  14.     {
  15.         output[temp[array[i]]-1] = array[i];    //放到对应位置上
  16.         temp[array[i]] -= 1;    //个数剪1
  17.     }
  18.     return output;
  19. }

测试一下

  1. int main()
  2. {
  3.     vector<int> array = { 2,5,3,0,2,3,0,3 };
  4.     vector<int> output;
  5.     output=counting_sort(array,5);
  6.     for each (int i in output)
  7.     {
  8.         cout << i << " ";
  9.     }
  10. }

输入仍然和书本上的例子相同，输出:

0 0 2 2 3 3 3 5

发表评论

表情：
评论列表 （有 0 条评论，240人围观）

还没有评论，来说两句吧...

相关阅读

    相关 排序算法——计数排序

    排序算法——计数排序 > 计数排序是一个非基于比较的排序算法。它的优势在于在对一定范围内的整数排序时，快于任何比较排序算法。 这是一种牺牲空间换取时间的做法，当O(k)>

    绝地灬酷狼绝地灬酷狼/ 0 赞/ 333 阅读

    相关 排序算法 —— 计数排序

    引言 计数排序是桶排序思想的一种具体实现，针对一些具有特殊限制的样本数据，如公司员工年龄，那么样本数据本身就一定在0~200之间，针对这样的数据，使用从0到200 的桶数

    我就是我我就是我/ 0 赞/ 297 阅读

    相关 算法导论：c++归并排序

    基本思想就是把数组一直分成两半，然后对这两半进行排序归并。 先分成左右两半，然后合并时比较左右两半一直选最小的替代原数组。这种排序是非原址的，需要额外的空间。 伪代码非

    偏执的太偏执、偏执的太偏执、/ 0 赞/ 263 阅读