计数排序 C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
//计数排序
using namespace std;
int GetMax(int a[],int n)
{
int max=a[0];
for(int i=1;i<n;i++){
if(a[i]>max)
max = a[i];
}
return max;
}
void countsort(int a[],int n)
{
int m = GetMax(a,n);
int b[m+1]={0};
for(int j=0;j<n;j++)
b[a[j]]++;
for(int i=0,k=0;i<=m||k<n;i++)
{
while(b[i]>0){
a[k++] = i;
b[i]--;
}
}
}
int main()
{
int a[30] = {1,3,5,7,8,10,12,11,19,8,15,13,12,17,2,4,6,8,9,10,11,19,18,13,12,54,32,11,56,21};
cout<<"before sort"<<endl;
for(int i =0 ;i<30;i++) cout<<a[i]<<" ";
cout<<endl;
countsort(a,30);
for(int i=0;i<30;i++)
cout<<a[i]<<" ";
/*int b[21]={0};
for(int i =0;i<25;i++)
b[a[i]]++;
for(int j=0;j<=20;j++)
{
while(b[j]>0){
cout<<j<<" ";
b[j]--;
}
}
*/
return 0;
}