计数排序
2012-12-30 13:00:18 最后更新: 2015-08-06 18:49:56 访问数量：1273
算法说明
基于比较的排序算法的本质都是基于决策树的，由于树的高度为O(logn)，所以基于比较的排序算法在最坏情况下其时间复杂度不会低于O(nlogn)
而计数排序并不是基于比较的，而是通过循环计数确定每个元素排序后的位置，而进行的一种排序
其算法思路如下：
代码
/*
* file: main.c
* author: 龙泉居士
* date: 2012-12-30 13:00
*/
#include <stdio.h>
#include <malloc.h>
int counting_sort (int *array, int n, int count)
{
if (array == NULL || n<=0 || count <= 0)
{
printf ("counting_sort param error\n");
return -1;
}
int *tmp = (int *)malloc((count+1)*sizeof(int));
if (tmp == NULL)
{
printf ("malloc error\n");
return -1;
}
int i;
for (i=0; i<=count; ++i)
tmp[i] = 0;
for (i=0; i<n; ++i)
tmp[array[i]]++;
for (i=1; i<=count; ++i)
tmp[i] += tmp[i-1];
int *tmparray = (int *)malloc(n*sizeof(int));
for (i=0; i<n; ++i)
{
tmparray[tmp[array[i]]-1] = array[i];
-- tmp[array[i]];
}
for (i=0; i<n; ++i)
array[i] = tmparray[i];
free (tmparray);
free (tmp);
return 0;
}
int main ()
{
int i, n=0, m=0;
int array[256];
printf ("Please input numbers, end by 9999:\n");
while (1)
{
scanf ("%d", &array[n]);
if (array[n] == 9999)
break;
if (array[n] > m)
m = array[n];
++n;
}
if (counting_sort(array, n, m))
return -1;
for (i=0; i!=n; ++i)
printf ("%d ", array[i]);
printf ("\n");
return 0;
}
错误
算法代码中的第30行的地方，应该使用倒序的方式遍历数组array、填充tmparray。
为什么呢？因为tmp中的序号是以减小的方式变化的，所以，如果使用正序遍历array，那么，将无法保证数据的稳定性，即原来相等但在前面的数字在排序后将会处于后面
这会造成什么问题呢？也许在这个例子中无法发现这个问题的严重性，但是在radix_sort的应用中，这就很明显了，因为在每次局部的使用counting_sort排序时，对counting_sort来说相同的数据实际上并不相同，事实上，radix_sort中可以应用counting_sort正是因为counting_sort的稳定性
微信公众号
欢迎关注微信公众号，以技术为主，涉及历史、人文等多领域的学习与感悟，每周三到七篇推文，只有全部原创，只有干货没有鸡汤
