计数排序(Counting-Sort)

ゝ一纸荒年。 2022-05-16 11:20 168阅读 0赞

计数排序的思想是在一个预排序的整数集中，统计每一个整数在这个整数集中小于等于本身的整数个数，这样的话，就得到了预排序整数集中每个数的在已排序集中的位置，

然后将预排序集与预排序集所处的位置对应起来，每次已排序一个，则将该计数减一（原因是存在相同的整数）。

例如：已知预排序集A=\{0,2,4,2,3,4\},可知最大数为4，则可以申请空间为4的数组C和C'。

*  step1:统计每个数的个数，得C'\[0\]=1，C'\[1\]=0，C'\[2\]＝2，C'\[3\]＝1，C'\[4\]＝2，即C'\[0\]+...+C'\[4\]=预排序的整数总个数；
 *  step2:根据C'，计算每一个整数小于等于本身的整数个数，C\[0\]=1，C\[1\]=1，C\[2\]＝3，C\[3\]＝4，C\[4\]＝6；
 *  step3:遍历预排序集，根据数组C找到每一个整数所在的位置，从而得到已排序的数据集S，以A\[0\]=0为例，由于C\[A\[0\]\]＝C\[0\]=1，所以0所在的位置是S中的第一个数，然后C\[0\]减一，同理，A\[1\]=2，由于C\[A\[1\]\]＝C\[2\]=3，所以0所在的位置是S中的第三个数，然后C\[2\]减一，一直到最后一个整数，算法结束。

PS：该算法的优点在于时间复杂为O(n)，不需要在数据之间进行比较，但是如果数据分布很分散，则需要的空间会很大，比如1,2,100,155555.

由此可得，空间和时间是两个互补的概念，用空间换取时间，用时间换取空间。

附C程序源代码：

\#include "stdio.h"  
\#include "stdlib.h"

void count\_sort(int data\[\],int max,int len)  
\{  
 int\* counter = NULL;  
    counter = (int\*)malloc(sizeof(int) \* max);//申请计数器空间  
 int i=0;  
 for(i=0;i<=max;i++)  
 \{  
  counter\[i\]=0;//初始化计数器  
 \}  
 for(i=0;i<len;i++)  
 \{  
  counter\[data\[i\]\]++;//统计每个数的个数  
 \}  
 for(i=1;i<=max;i++)  
 \{  
  counter\[i\]+=counter\[i-1\];//统计小于等于本身的整数个数  
 \}  
 int\* sorted = NULL;  
    sorted = (int\*)malloc(sizeof(int) \* len);//申请已排序数据空间  
 for(i=0;i<len;i++)  
 \{  
  sorted\[counter\[data\[i\]\]-1\]=data\[i\];//将预排序数据对应到计数器中  
  counter\[data\[i\]\]--;  
 \}  
 //输出  
 printf("unsorted datasets:\\n");  
 for(i=0;i<len;i++)  
  printf("%d ",data\[i\]);  
 printf("\\n");  
 printf("sorted datasets:\\n");  
 for(i=0;i<len;i++)  
  printf("%d ",sorted\[i\]);  
 printf("\\n");  
\}

int main(void)  
\{  
 int data\[6\]=\{0,2,4,2,3,4\};//预排序数据集  
 count\_sort(data,4,6);  
 return 0;  
\}