#include"RADIX_SORT_GET_WZ.h"

 1 #pragma once
 2 #include<vector>
 3 #include<algorithm>
 4 #include<string>
 5 #include<sstream>  //stringstream
 6 #include<iomanip> //setw setfill
 7 //内置变量pass-by-value more than pass-by-reference ? 
 8 //P12 --Effective C++(Chinese)
 9 
10 //d位数，A数字
11 int get_d(const std::vector<int>& A)
12 {
13     int max = *std::max_element(A.cbegin(), A.cend());
14     int d = 0;
15     for (int i = max; i != 0;d++)
16     {
17         i /= 10;
18     }
19     return d;
20 }
21 
22 int get_ws(const std::vector<int>& A, int j,int ws)
23 {
24     int d = get_d(A);
25     auto s = std::to_string(A[j]);
26     std::stringstream ss;
27     ss << std::left << std::setfill(‘0‘) << std::setw(d + 1) << s;
28     s = ss.str();
29     ss << std::right << std::setfill(‘ ‘);
30     int k = s[ws] - ‘0‘;
31     return k;
32 }
33 //k:A数组中最大值，ws： 对A的的第几位排序 A[ws]
34 void Count_sort_wz(std::vector<int>& A, const int k, int ws)
35 {
36 //    ws = pow(10, ws);
37     std::vector<int> c(k + 1);
38     for (int j = 0;j != A.size();++j)
39         ++c[get_ws(A,j,ws)];
40     for (int i = 1;i <= k;++i)
41         c[i] += c[i - 1];
42     std::vector<int> b(A.size());
43     for (int i = A.size() - 1;i >= 0;--i)
44         b[--c[get_ws(A,i,ws)]] = A[i];
45     for (int i = 0; i != A.size();++i)
46         A[i] = b[i];
47 }
48 
49 
50 void Radix_Sort(std::vector<int>& A)
51 {
52     int max = *std::max_element(A.cbegin(), A.cend());
53     int d = get_d(A);
54     for (int ws = 0;ws != d; ++ws)
55     {
56         //max 这时为0
57         Count_sort_wz(A, max, ws);
58     }
59 }