#include <iostream>
#include <vector>
using namespace std;
template<class T>
void raixSort(T &arr) {
vector<vector<int>> bucket(10, vector<int>());
int max = 0;
for (int i = 0; i < arr.size(); i++) {
max = arr[i] > max ? arr[i] : max;
}
for (int n = 1; n < max; n = n * 10) {
for (int i = 0; i < arr.size(); i++) {
int d = arr[i] / n % 10;
bucket[d].push_back(arr[i]);
}
int index = 0;
for (int k = 0; k < bucket.size(); k++) {
if(!bucket[k].empty()){
for (int j = 0; j < bucket[k].size(); j++) {
arr[index++] = bucket[k][j];
}
}
}
for (int i = 0; i < bucket.size(); i++) {
bucket[i].clear();
}
}
}
int main() {
vector<int> arr{ 10,2,50,42,50,48,2,1,852,7,554,568,56,63,621,96 };
raixSort(arr);
for (auto i = arr.begin(); i != arr.end(); i++) {
cout << *i << " ";
}
cout << endl;
system("pause");
}
Processed:
0.008, SQL:
10
