基数排序

基数排序，不是基于比较的排序。

过程如下：

处理过程：

 桶排过程：

 1 void Bucket_sort(int a[],int exp)//exp为1按个位排序，exp为10按十位排序，exp为100按个位排序，…… 
 2 {
 3     vector<int>Bucket[20]; 
 4     
 5     //按位入桶 ，+10 是为了对付负数 
 6     for(int i=0;i<n;i++){
 7         int pos=a[i]/exp%10;
 8         Bucket[pos+10].push_back(a[i]);
 9     }
10     
11     //将每个桶中的数安顺序还给数组 
12     int k=0;
13     for(int pos=0;pos<=19;pos++) //升序，若要倒序可以反过来给数组。 
14     {
15        for(int j=0;j<Bucket[pos].size();j++){
16                a[k++]=Bucket[pos][j];
17        }
18     } 
19 }

整体代码：

 1 /*
 2 
 3 16
 4 -53 -3 -54 74 48 18 -24 54 63 663 -9 9 19 -9999 0 789 
 5 
 6 
 7 before sort:-53 -3 -54 74 48 18 -24 54 63 663 -9 9 19 -9999 0 789
 8 after  sort:-9999 -54 -53 -24 -9 -3 0 9 18 19 48 54 63 74 663 789
 9 
10 */
11 
12 
13 #include<bits/stdc++.h>
14 using namespace std;
15 #define LL long long
16 
17 const int N = 255;
18 int a[N];
19 int n; 
20 
21 int getmax(int a[]){
22     int maxa=abs(a[0]);
23     for(int i=1;i<n;i++) maxa=max(maxa, abs(a[i]));
24     return maxa;
25 }
26 
27 void Bucket_sort(int a[],int exp)
28 {
29     vector<int>Bucket[20]; 
30     
31     //按位入桶 +10 是为了对付负数 
32     for(int i=0;i<n;i++){
33         int pos=a[i]/exp%10;
34         Bucket[pos+10].push_back(a[i]);
35     }
36     
37     //将每个桶中的数安顺序倒给数组 
38     int k=0;
39     for(int pos=0;pos<=19;pos++) //升序，若要倒序可以反过来给数组。 
40     {
41        for(int j=0;j<Bucket[pos].size();j++){
42                a[k++]=Bucket[pos][j];
43        }
44     } 
45 }
46 
47 
48 int main()
49 {
50     cin>>n;
51     for (int i=0; i<n; i++) cin >> a[i] ;
52     
53     cout << "before sort:";
54     for (int i=0; i<n; i++) cout << a[i] << " ";
55     cout << endl;
56     
57     
58     //基数排序 
59     int maxa=getmax(a);
60     for(int exp=1;maxa/exp>0;exp*=10)
61         Bucket_sort(a,exp);
62     
63     cout << "after  sort:";
64     for (int i=0; i<n; i++) cout << a[i] << " ";
65     cout << endl;
66     
67 
68 
69     return 0;
70 }