C语言必学的12个排序算法：计数排序（第9篇）

分手后的思念是犯贱 2023-03-04 11:24 17阅读 0赞

\#\#\#\#题外话计数排序时间性能比之前的排序算法高，在实际中应用较多，只需要O(n)时间即可完成排序。计数排序思想比较巧妙，建议大家对照课本多学习，本文主要给出能运行的实例程序。

\[C语言必学的12个排序算法：基础知识 (第0篇）\]

# 线性时间排序 #

之前学习的快速排序、堆排序、归并排序都是一类基于比较的排序算法，需要通过比较关键字大小确定数据元素的位置。这类算法最优的时间复杂度只能到O(nlogn)。

线性时间排序是一类非比较排序算法，时间复杂度O(n)，不需要通过比较关键字大小即可完成排序。计数排序(counting sort)是其中一种。

# 计数排序基本思想 #

基本思想是给定一个待排的整数序列，对于每一个数据元素，直接存放在保存排序结果的数组对应下标的位置，例如数据元素为5时，直接存放到数组a\[5\]位置，数据元素为0时，直接存放到数组a\[0\]的位置。这样利用待排的数据元素和数组内存地址位置建立一一对应关系，由于数组内存分配是从小到大连续分配，因此最后直接输出数组，即可获得有序的整数序列。

计数排序对于输入的数据元素类型有要求，一般是小范围的整数或字符，或者很方便利用数据元素本身和内存地址建立意义对应关系。对于n个整数输入序列，确定每个数据元素取值范围\[0-k\]，当k值小于等于n时，其时间复杂度是O(n)，需要的辅助空间是O(k)，当n很小也就是数据量很小，但是n取值范围很大也就是k值很大时，不适合使用计数排序，因为内存空间浪费严重，时间复杂度也变成O(k)。

考虑到待排数据记录关键字有重复，会出现多次，为保证排序结果的稳定性，因此计数排序需要对出现多次关键字的数据进行计数，保存到数组对应下标的位置，并且根据该数组计数进一步计算其在排序后的序列的位置。

# 代码实现 #

本实例代码实现要点：

1.数组a\[\]保存待排的整数数据记录，数据记录本身就是关键字，每个整数的取值范围\[0-k\]，最大取值为k。

2.数组c\[\]临时保存每个整数出现的次数，如果没有出现值为0，利用内存动态分配，大小为k。

3.数组b\[\]用来临时保存排序后的整数数据记录，最终将数组b\[\]的排序结果复制到数组a\[\]，方便封装使用。

3.对数组c\[\]的计数进行累加统计，从而确定每个数据元素在数组b\[\]的位置，特别是重复出现的数据，在数组b\[\]中将是一段位置。

/*
    #include <stdio.h>
    #include <stdlib.h>
    
    
    void counting_sort(int a[], int length, int k)
    {
      // 使用calloc会自动初始化为0
      // 数组b临时保存排序后的数据记录 
      int *b = (int *)calloc(length, sizeof(int));
      // 数组c对数据记录关键字进行计数 
      int *c = (int *)calloc(k, sizeof(int));
      
      int i;
      // 每出现1个数据记录，对应的数组位置+1 
      // c[i]表示数据等于i的元素个数 
      for(i=0; i<length; i++)
        c[a[i]] = c[a[i]] + 1;
      
      // 对数组C的计数累累加确定排序后位置
      // c[i]表示小于等于i值的数据元素个数
      for(i=1; i<k; i++)
        c[i] = c[i] + c[i-1]; 
      
      // 将排序结果输出到临时数组b中
      for(i=length-1; i>=0; i--)
      {
        // 注意数组b数组下标从0开始
        // 计算的实际位置-1 
        b[c[a[i]]-1] = a[i];
        // 如果数据元素重复出现 
        // 将该元素下一个保存位置前移 
        c[a[i]] = c[a[i]] - 1;
      } 
      
      // 复制到数组a中
      for(i=0; i<length; i++)
        a[i] = b[i]; 
      
      free(b);
      free(c);
    }
    int main(void)
    {
        int a[14] = {4,3,1,2,6,5,0,9,8,7,1,3,0,1};
        counting_sort(a, 14, 10);
        int i;
        for(i=0; i<14; i++)
          printf("%d ", a[i]);
        return 0;
    }

其实做为一个学习者，有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C/C++基础交流583650410，不管你是小白还是转行人士欢迎入驻，大家一起交流成长。  
![format_png][]  
![format_png 1][]

[format_png]: /images/20230208/1da993e12359425c837aa4d33afb37cf.png
[format_png 1]: /images/20230208/d47ae73ee3d84921b1b78a9850bcf499.png