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

妖狐艹你老母 2022-06-10 02:52 197阅读 0赞

**计数排序**

像快排、堆排、归并等排序算法都是基于比较的排序算法，时间复杂度最好情况也只能降到O(nlogn)。

**计数排序**是一种线性排序算法，不需要进行比较，时间复杂度为O(n)。（注意是计数排序不是基数排序，两者不同）

基本思想是：对于每个元素x，找出比x小的数的个数，从而确定x在排好序的数组中的位置。此算法需要辅助数组，是以空间换时间。

举例说明：

原始数组：arr

<table style="border-collapse:collapse; margin-left:0px; table-layout:fixed; width:38.368580060422964%"> 
 <tbody> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:9.448818897637794%"> 
    <div style="text-align:center">
      1 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:9.448818897637794%"> 
    <div style="text-align:center">
      5 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:9.448818897637794%"> 
    <div style="text-align:center">
      3 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:9.448818897637794%"> 
    <div style="text-align:center">
      7 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:9.251968503937007%"> 
    <div style="text-align:center">
      6 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:9.05511811023622%"> 
    <div style="text-align:center">
      2 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:8.267716535433072%"> 
    <div style="text-align:center">
      8 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:8.858267716535433%"> 
    <div style="text-align:center">
      9 
    </div> </td> 
   <td style="border:1px solid rgb(211,211,211); padding:10px; margin:0px; width:8.858267716535433%"> 
    <div style="text-align:center">
      4 
    </div> </td> 
   <td style="border:1px solid rgb(211,211,211); padding:10px; margin:0px; width:8.858267716535433%"> 
    <div style="text-align:center">
      3 
    </div> </td> 
   <td style="border:1px solid rgb(211,211,211); padding:10px; margin:0px; width:8.858267716535433%"> 
    <div style="text-align:center">
      3 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

其中最大的元素为9，那么就申请一个大小为9的辅助数组count作为计数数组，同时拷贝一份原始数组元素tmp,

辅助数组tmp

<table style="border-collapse:collapse; margin-left:0px; table-layout:fixed; width:38.368580060422964%"> 
 <tbody> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:9.448818897637794%"> 
    <div style="text-align:center">
      1 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:9.448818897637794%"> 
    <div style="text-align:center">
      5 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:9.448818897637794%"> 
    <div style="text-align:center">
      3 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:9.448818897637794%"> 
    <div style="text-align:center">
      7 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:9.251968503937007%"> 
    <div style="text-align:center">
      6 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:9.05511811023622%"> 
    <div style="text-align:center">
      2 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:8.267716535433072%"> 
    <div style="text-align:center">
      8 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:8.858267716535433%"> 
    <div style="text-align:center">
      9 
    </div> </td> 
   <td style="border:1px solid rgb(211,211,211); padding:10px; margin:0px; width:8.858267716535433%"> 
    <div style="text-align:center">
      4 
    </div> </td> 
   <td style="border:1px solid rgb(211,211,211); padding:10px; margin:0px; width:8.858267716535433%"> 
    <div style="text-align:center">
      3 
    </div> </td> 
   <td style="border:1px solid rgb(211,211,211); padding:10px; margin:0px; width:8.858267716535433%"> 
    <div style="text-align:center">
      3 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

然后遍历整个原始数组元素，将元素作为count的下标，统计每个元素出现的次数。

辅助数组count

<table style="border-collapse:collapse; margin-left:0px; table-layout:fixed; width:38.40417598806861%"> 
 <tbody> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:10.29126213592233%"> 
    <div style="text-align:center">
      0 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:10.29126213592233%"> 
    <div style="text-align:center">
      1 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:10.29126213592233%"> 
    <div style="text-align:center">
      1 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:10.29126213592233%"> 
    <div style="text-align:center">
      3 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:10.29126213592233%"> 
    <div style="text-align:center">
      1 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:10.097087378640776%"> 
    <div style="text-align:center">
      1 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:9.12621359223301%"> 
    <div style="text-align:center">
      1 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:9.70873786407767%"> 
    <div style="text-align:center">
      1 
    </div> </td> 
   <td style="border:1px solid rgb(211,211,211); padding:10px; margin:0px; width:9.70873786407767%"> 
    <div style="text-align:center">
      1 
    </div> </td> 
   <td style="border:1px solid rgb(211,211,211); padding:10px; margin:0px; width:9.70873786407767%"> 
    <div style="text-align:center">
      1 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

接着遍历count数组，对于每个元素x，计算出比x小的元素的个数，即count\[i\]=count\[i\]+count\[i-1\]。

辅助数组count

<table style="border-collapse:collapse; margin-left:0px; table-layout:fixed; width:38.368580060422964%"> 
 <tbody> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:10.433070866141732%"> 
    <div style="text-align:center">
      0 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:10.433070866141732%"> 
    <div style="text-align:center">
      1 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:10.433070866141732%"> 
    <div style="text-align:center">
      2 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:10.236220472440944%"> 
    <div style="text-align:center">
      5 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:10.236220472440944%"> 
    <div style="text-align:center">
      6 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:10.039370078740157%"> 
    <div style="text-align:center">
      7 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:9.05511811023622%"> 
    <div style="text-align:center">
      8 
    </div> </td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:9.645669291338582%"> 
    <div style="text-align:center">
      9 
    </div> </td> 
   <td style="border:1px solid rgb(211,211,211); padding:10px; margin:0px; width:9.645669291338582%"> 
    <div style="text-align:center">
      10 
    </div> </td> 
   <td style="border:1px solid rgb(211,211,211); padding:10px; margin:0px; width:9.645669291338582%"> 
    <div style="text-align:center">
      11 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

然后遍历整个原始数组元素，将对应的数字放入最终的位置上。

代码如下：

#include <iostream>
    #include <vector>
    using namespace std;
    
    void CountSort(vector<int> &arr, int maxVal) {
    	int len = arr.size();
    	if (len < 1)
    		return;
    	vector<int> count(maxVal+1, 0);
    	vector<int> tmp(arr);
    	for (auto x : arr)
    		count[x]++;
    	for (int i = 1; i <= maxVal; ++i)
    		count[i] += count[i - 1];
    	for (int i = len - 1; i >= 0; --i) {
    		arr[count[tmp[i]] - 1] = tmp[i];
    		count[tmp[i]]--;				//注意这里要减1
    	}
    }
    
    int main()
    {
    	vector<int> arr = { 1,5,3,7,6,2,8,9,4,3,3 };
    	int maxVal = 9;
    	CountSort(arr,maxVal);
    	for (auto x : arr)
    		cout << x << " ";
    	cout << endl;
    	return 0;
    }

运行结果如下：

![Center][]

此算法适合最大值不大的情况，如果元素个数n不大，但是最大值很大，会造成空间浪费

[Center]: /images/20220610/3aeade54b9b44d86b64030a939c44f2f.png

发表评论取消回复

表情：

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

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

相关阅读

相关排序算法-计数排序

排序算法-计数排序

柔光的暖阳◎/ 2024年05月02日 20:26/ 0 赞/ 82 阅读

相关十大排序算法之计数排序

题：对a\[\]=\{3,44,38,5,47,15,36,26,27,2,46,4,19,50,48\}排序要求从小到大排列。介绍：这个应该是一...

╰半橙微兮°/ 2024年04月19日 08:35/ 0 赞/ 81 阅读

相关排序算法 - 计数排序

基本思想计数排序是一种线性排序算法，它利用了一个数组，因为数组下标的增长是线性的，所以它就把自己的元素转换成新开辟数组的下标。可是下标都是非负数啊？数组当中的值有正有负

柔光的暖阳◎/ 2023年08月17日 16:43/ 0 赞/ 77 阅读

相关排序算法之计数排序

\[非比较排序-计数排序\] 1.算法思想计数排序要求数据必须是有确定范围的整数，需要定义一个新的数组，新数组的长度是根据原数组最大值和最小值来确定的，该数组用

柔光的暖阳◎/ 2022年12月31日 01:09/ 0 赞/ 204 阅读

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

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

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

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

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

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

相关排序算法之计数&基数排序

计数排序> 给定一组待排序的数据，找到这组数据中的最大值，然后开辟一个最大值加1的数组，用memset初始化为全0，然后再次遍历原数组，使得这个新开辟的数组中存储的是该数字

曾经终败给现在/ 2022年07月14日 08:00/ 0 赞/ 242 阅读

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

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

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

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

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

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

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

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

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