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

今天药忘吃喽~ 2022-06-04 02:54 186阅读 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 条评论，186人围观）

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

相关阅读

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

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

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

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

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

我就是我/ 2022年10月16日 12:29/ 0 赞/ 216 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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