|
#include
#include
#include
#define NR(x) sizeof(x)/sizeof(x[0])
//计数排序
//排序成功返回0，否则返回⑴
//局限:只能用于整型或那些可以用整型来表示的数据集合
//优点：速度快，稳定
/*
利用计数排序将数组data中的整数进行排序。
data中的元素个数由sized决定。
参数k为data最大的整数加1，当ctsort返回时，k为data中最大的整数加1
复杂度:O(n+k),N为要排序的元素个数,k为data中最大的整数加1
*/
int ctsort(int *data,int size,int k)
{
int *counts,*temp;
int i,j;
if ((counts = (int *)malloc(k * sizeof(int))) == NULL)
return ⑴;
if ((temp = (int *)malloc(size * sizeof(int))) == NULL)
return ⑴;
for (i = 0; i < k; i++) counts[i] = 0; for (j = 0; j < size; j++) counts[data[j]] = counts[data[j]] + 1; for (i = 1; i < k; i++) counts[i] = counts[i] + counts[i - 1]; for (j = size - 1; j >= 0; j--) {
temp[counts[data[j]] - 1] = data[j];
counts[data[j]] = counts[data[j]] - 1;
}
memcpy(data,temp,size * sizeof(int));
free(counts);
free(temp);
return 0;
}
int main(void)
{
int buffer[10] = {1,3,2,7,4,8,9,22,12,13} ;
int i ;
ctsort(buffer,NR(buffer),23) ;
for(i = 0 ; i < NR(buffer) ; i++) printf("buffer[%d]:%dn",i,buffer[i]) ; return 0 ; }
运行结果:
buffer[0]:1
buffer[1]:2
buffer[2]:3
buffer[3]:4
buffer[4]:7
buffer[5]:8
buffer[6]:9
buffer[7]:12
buffer[8]:13
buffer[9]:22
--------------------------------
Process exited after 0.04599 seconds with return value 0
请按任意键继续. . .
（编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
