<排序算法> 计数排序CountSort

 1 #include<iostream>
 2 using namespace std;
 3 
 4 void PrintArr(int arr[],int len);
 5 void CountSort(int arr[],int len)
 6 {
 7     if(arr == NULL || len <= 0)    return ;
 8     
 9     int min = arr[0];
10     int max = arr[0];
11     int i;
12     for(i=0;i<len;i++)
13     {
14         if(arr[i] < min)
15             min = arr[i];
16         if(arr[i] > max)
17             max = arr[i];
18     }
19 
20     int* arrcount = (int*)malloc(sizeof(int)*(max-min+1));
21     memset(arrcount,0,sizeof(int)*(max-min+1));
22     for(i=0;i<len;i++)
23     {
24         arrcount[arr[i]-min] ++;
25     }
26 
27     int j=0;
28     for(i=0;i<max-min+1;i++)
29     {
30         if(arrcount[i] != 0)
31             while(arrcount[i]--)
32                 arr[j++] = i + min;
33     }
34 
35     return ;
36 }
37 
38 void PrintArr(int arr[],int len)
39 {
40     for(int i=0;i<len;i++)
41         cout << arr[i] << " ";
42     cout << endl;
43 
44     return ;
45 }
46 
47 int main()
48 {
49     //int arr[10] = {9,8,7,6,5,4,3,2,1,0};
50     //int arr[10] = {4,8,6,3,7,2,9,5,0,1};
51     int arr[10] = {4,4,2,3,3,8,8,8,5,5};
52     CountSort(arr,sizeof(arr)/sizeof(arr[0]));
53     PrintArr(arr,sizeof(arr)/sizeof(arr[0]));
54 
55     system("pause");
56     return 0;
57 }