学习笔记-详解计数排序

大家好，欢迎来到IT知识分享网。

本文目的

上一章节已经详细的向大家介绍过排序的相关概念（学习笔记-排序简单介绍） ，本文旨在为大家详细的介绍计数排序。

计数排序

计数排序和原来说过的几个排序算法最大的不同之处：它是一个不基于比较的排序算法。该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）。它也有很大的局限性，比如它只能对整数进行排序。总之，计数排序是一种对整数进行排序非常有效的排序算法。比较性质排序算法的时间复杂度有一个理论边界，即 O(n*log(n))。n个元素的序列，能够形成的所有排列个数为n!，即该序列构成的决策树叶子节点个数为 n!，由叶子节点个数可知，决策树的高度为log(n!)，即由决策树根节点到叶子节点的比较次数为log(n!)，由公式转换可得，比较性质的算法复杂度理论边界为O(n*log(n)) 。

算法思想

计数排序对输入的数据有附加的限制条件：

1、输入的线性表的元素属于有限偏序集S；

2、设输入的线性表的长度为n，|S|=k（表示集合S中元素的总数目为k），则k=O(n)。

在这两个条件下，计数排序的复杂性为O(n)。

计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同一个位置上。

计数排序更像一种哈希算法，将待排序的数据根据指定的函数分配至指定的空间，从而达到排序的目的。

算法过程

1, 根据待排序集合中最大元素和最小元素的差值范围，申请额外空间；

2, 遍历待排序集合，将每一个元素出现的次数记录到元素值对应的额外空间内；

3, 对额外空间内数据进行计算，得出每一个元素的正确位置；

4, 将待排序集合每一个元素移动到计算得出的正确位置上。

排序示例

原始序列：{1,3,2.1,4,5,2.4,1,1,3,4}

第一步：计算所需空间

计算空间方法很简单，直接max-min+1即可。

序列中最大值为：max=5，最小值为：min=1，根据序列中最大值和最小值的差值范围，可得申请额外空间大小为：max-min=5-1+1=5

第二步：元素统计

因为申请的额外空间足以存放min至max之间的所有元素记录，所以将待排序集合中每一个元素都记录到额外空间上。例如元素 5，对应的记录位置下标为index=5-min=4,即最后一个位置，将所有元素都进行此种地址映射。其中index表示索引，value表示元素值

此时我们会发现一个问题，那就是如果某个元素出现多次，那么怎么存放呢，顺序存放可能会导致空间不足和映射关系混乱。因此我们就引入了另外一个存储。即value-count,每个元素和其出现次数对应表。

所有元素的出现次数和元素值记录如下，其中count表示该元素出现的次数，value表示元素值：

可以发现，计数排序的该过程，其实就是将待排序集合中的每个元素值本身大小作为下标，依次进行了存放。而记录的count，就是为了确定该元素值出现了几次。

第三步：元素归位

记录每个元素出现的次数，并对次数做计算，作用是当移动待排序集合元素到已排序集合中时，确保相同元素都被移动，且保持算法稳定性。因为额外空间中元素值是有序排列的，即额外空间的序列中每个元素，其元素的最终位置都是在前一个元素的后面，所以将其中每个元素的次数更新为加上前一个元素的次数和。

第四步：排序完成

根据额外空间已经确定的元素序列，移动待排序集合元素到已排序集合中。

算法实现

#include 
  
    #include 
   
     #define elemType int /*元素类型*/ #define MAX 9 //元素个数 int k=1;//轮次记录 //打印函数 void Print (elemType arr[], int len){ int i; for (i=0; i<len; i++){ printf ("%d\t", arr[i]); } printf("\n"); } void Sort(elemType arr[], int len) { int i,j,count,temp; elemType *data_p; data_p=(int*)malloc(sizeof(int)*len); for(i=0;i<len;i++)//初始化data_p data_p[i]=0; for(i=0;i<len;i++) { count=0; for(j=0;j<len;j++) //扫描待排序数组 if(arr[j]<arr[i]) //统计比data[i]值小的值的个数 count++; while(data_p[count]!=0) //对于相等非0的数据，应向后措一位。数据为0时，因数组data_p被初始化为0，故不受影响。 /* 注意此处应使用while循环进行判断，若用if条件则超过三个重复值后有0出现 */ count++; data_p[count]=arr[i]; //存放到data_p中的对应位置 } //用于检查当有多个数相同时的情况 i=0,j=len; while(i<j) { if(data_p[i]==0) { temp=i-1; data_p[i]=data_p[temp]; }//of if i++; }//of while for(i=0;i<len;i++)//把排序完的数据复制到data中 arr[i]=data_p[i]; free(data_p);//释放data_p } void main() { int i; elemType arr[MAX] = {94,19,29,9,11,1,14,13,29}; printf("待排序的序列为：\n"); Print(arr, MAX); printf("\n\n"); Sort (arr,MAX); printf("\n\n"); printf("排好序的结果如下：\n"); Print(arr, MAX); } 
    
  

算法分析

由算法示例可知，计数排序的时间复杂度为Ο(n+k)。因为算法过程中需要申请一个额外空间和一个与待排序集合大小相同的已排序空间，所以空间复杂度为Ο(n+k)。由此可知，计数排序只适用于元素值较为集中的情况，若集合中存在最大最小元素值相差甚远的情况，则计数排序开销较大、性能较差。通过额外空间的作用方式可知，额外空间存储元素信息是通过计算元素与最小元素值的差值作为下标来完成的，若待排序集合中存在元素值为浮点数形式或其他形式，则需要对元素值或元素差值做变换，以保证所有差值都为一个非负整数形式。计数排序是一种稳定的排序

本文的初衷为学习笔记的分享，部分图文来源于网络，如侵，联删。