计数排序

2012-12-30 13:00:18   最后更新: 2015-08-06 18:49:56   访问数量:579




基于比较的排序算法的本质都是基于决策树的,由于树的高度为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的稳定性

 






读书笔记      技术帖      算法      算法导论      龙潭书斋      排序      sort      计数排序      计数      count      countsort     


京ICP备15018585号