Chinaunix首页 | 论坛 | 博客
  • 博客访问: 233616
  • 博文数量: 127
  • 博客积分: 34
  • 博客等级: 民兵
  • 技术积分: 655
  • 用 户 组: 普通用户
  • 注册时间: 2012-10-03 10:53
文章分类

全部博文(127)

文章存档

2013年(19)

2012年(108)

分类:

2012-11-21 23:58:41

原文地址:计数排序 作者:DBOYaoao


点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. int data[8] = {5,6,7,8,4,3,2,1};

  5. void sort(int k)
  6. {
  7.     int *countarray = (int*)malloc((k+1)*4);
  8.     if(!countarray)
  9.     {
  10.         printf("create countarray error\n");
  11.         return ;
  12.     }
  13.     memset(countarray,0,(k+1)*4);
  14.     int size = sizeof(data) / 4;
  15.     int i = 0;
  16.     while(i < size)
  17.     {
  18.         countarray[data[i]]++;
  19.         i++;
  20.     }
  21.    
  22.     int p = 0;
  23.     while(p<(k+1))
  24.     {
  25.         countarray[p+1] = countarray[p+1] + countarray[p];
  26.         p++;
  27.     }
  28.     
  29.     int x = 0;
  30.     int *sortdata = (int*)malloc((k+1)*4);
  31.     if(!sortdata)
  32.     {
  33.         printf("create sortdata error\n");
  34.         return ;
  35.     }
  36.     while(x<size)
  37.     {
  38.         int tmp;
  39.         tmp = (--countarray[data[x]]);
  40.         sortdata[tmp] = data[x];
  41.         x++;
  42.     }

  43.     int j=0;
  44.     for(;j<size;j++)
  45.     {
  46.         printf("%d\n",sortdata[j]);
  47.     }

  48. }

  49. int main()
  50. {
  51.    sort(8);
  52.    return 0;
  53. }
时间复杂度O(n)
阅读(435) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~