不晓得哪个

计数排序

逻辑比较简单的算法,却用了比较长的时间来实现,主要时间花在三个数组边界上面了,代码很丑,将就了
 1 #include<stdio.h>
 2 #include<time.h>
 3 #include<stdlib.h>
 4 #define MAX 100
 5 #define MAX2 200
 6 #define RANDOM(x) (rand()%x)
 7 int * counting_sort(int *arr, int size)
 8 {
 9     int i,min,max=0,range;
10     int *temp,*des;
11     //min=max=arr[0];
12     for(i=0;i<size;i++)
13     {
14         if(arr[i]>max) max=arr[i];
15         //if(arr[i]>max)max=arr[i];
16         //if(arr[i]<min)min=arr[i];
17     }
18     range=max+1;
19     temp =(int *)malloc(range*sizeof(int));
20     des  =(int *)malloc(range*sizeof(int));
21 
22     for(i=0;i<range;i++)
23     {
24         temp[i]=0;
25     }
26     for(i=0;i<size;i++)
27     {
28         temp[arr[i]]+=1;
29     }
30     for(i=1;i<range;i++)
31     {
32         temp[i]=temp[i]+temp[i-1];
33     }
34 #if 0
35     printf("temp=");
36     for(i=0;i<range;i++)
37     {
38         printf("%d ",temp[i]);
39     }
40 #endif
41     for(i=size-1;i>=0;i--)
42     {
43         des[temp[arr[i]]]=arr[i];
44         temp[arr[i]]-=1;
45     }
46 return des;
47 }
48 int main()
49 {
50     int i=0;
51     int * arr=(int *)malloc(MAX*sizeof(int));
52     int * get;
53     srand(time(0));
54     for(i=0;i<MAX;i++)
55     {
56         arr[i]=RANDOM(MAX2);
57 //        printf("%d\t",arr[i]);
58     }
59     get=counting_sort(arr,MAX);
60         printf("\n");
61     for(i=1;i<=MAX;i++)
62         printf("%d\t",get[i]);
63     printf("\n");
64 }

posted on 2009-12-19 01:35 缘分游走 阅读(217) 评论(0)  编辑 收藏 引用 所属分类: 算法基础


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理