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

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

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

![这里写图片描述][SouthEast]

![这里写图片描述][SouthEast 1]

### 代码实现 ###

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

/*计数排序*/
    vector<int> counting_sort(vector<int> array,int k) //k表示数组中最大元素，output为输出
    {
        vector<int> temp(k+1,0);//临时数组，存放个数
        vector<int> output(array.size(), 0);//初始化输出
        for (int i = 0; i < array.size(); i++) {
            temp[array[i]] += 1;    //计算次数
        }
        for (int i = 1; i < temp.size(); i++)
        {
            temp[i] += temp[i - 1];     //计算个数
        }
        for (int i = array.size()-1; i >=0; i--)
        {
            output[temp[array[i]]-1] = array[i];    //放到对应位置上
            temp[array[i]] -= 1;    //个数剪1
        }
        return output;
    }

### 测试一下 ###

int main()
    {
        vector<int> array = { 2,5,3,0,2,3,0,3 };
        vector<int> output;
        output=counting_sort(array,5);
        for each (int i in output)
        {
            cout << i << " ";
        }
    }

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

> 0 0 2 2 3 3 3 5

[SouthEast]: /images/20220604/d09a823cfd554790862d779d1e493a99.png
[SouthEast 1]: /images/20220604/8b7e28d510cf4f2da0c9707df18dfa2b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，151人围观）

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

相关阅读

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

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

绝地灬酷狼/ 2022年12月23日 06:57/ 0 赞/ 171 阅读

相关算法导论之排序：快速排序、归并排序、计数排序、基数排序、桶排序

问题描述：输入：一个n个数的序列<a1,a2,a3,a4,a5,……,an>。输出：输入序列的一个排列<a1',a2',a3',a4',……,an'>。相关知识：

怼烎@/ 2022年07月28日 05:06/ 0 赞/ 185 阅读

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

前言计数排序的思想：在给定的数组中，依次寻找比当前数字小的元素的个数（count），统计之后直接使用t就可以定位到该数所在的位置，因为比它小的元素的个数已经通过coun

小鱼儿/ 2022年06月12日 00:44/ 0 赞/ 168 阅读

相关 C++排序算法之计数排序

计数排序像快排、堆排、归并等排序算法都是基于比较的排序算法，时间复杂度最好情况也只能降到O(nlogn)。计数排序是一种线性排序算法，不需要进行比较，时间复杂

妖狐艹你老母/ 2022年06月10日 02:52/ 0 赞/ 123 阅读

相关算法导论：c++桶排序

![这里写图片描述][SouthEast] 代码实现桶排序是按照桶的概念把元素往里面放，然后桶内还有一个排序，桶内排序可以用比较排序也可以用计数排序递归使用桶排序也可

客官°小女子只卖身不卖艺/ 2022年06月04日 04:29/ 0 赞/ 163 阅读

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

区别于比较排序需要元素进行相互比较，计数排序仅仅通过元素个数确定它在排序结果中的位置。 ![这里写图片描述][SouthEast] ![这里写图片描述][SouthEast

今天药忘吃喽~/ 2022年06月04日 02:54/ 0 赞/ 152 阅读

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

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

偏执的太偏执、/ 2022年06月04日 02:53/ 0 赞/ 151 阅读

相关算法导论：c++快速排序

快速排序也采用分治的思想，以最后一个元素为基准把其分成大于它和小于它的两部分，关键在于确定分割点。算法思想 ![这里写图片描述][SouthEast] 一趟快排

客官°小女子只卖身不卖艺/ 2022年06月04日 02:26/ 0 赞/ 178 阅读

相关《算法导论》——计数排序Counting Sort

　　今天贴出的算法是计数排序Counting Sort。在经过一番挣扎之前，我很纠结，今天这个算法在一些scenarios，并不是最优的算法。最坏情况和最好情况下，时间复杂度差

不念不忘少年蓝@/ 2021年12月09日 01:11/ 0 赞/ 180 阅读

相关排序算法c语言描述---计数排序

十。计数排序一。个人理解。计数排序假设n个输入元素中的每一个都是介于0到k之间的整数。计数排序的思想是对每一个输入元素x，确定出小于x的元素个数，有了这一信

ゝ一纸荒年。/ 2021年10月30日 05:04/ 0 赞/ 348 阅读