逻辑比较简单的算法,却用了比较长的时间来实现,主要时间花在三个数组边界上面了,代码很丑,将就了
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 }