算法精解—计数排序

#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]:%d\n”,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
请按任意键继续. . .

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 算法精解—计数排序

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡