3. 让你排序N个比N^7小的数,要求的算法是O(n)（给了提示..说往 N 进制那方面想）
/*
3. 让你排序N个比N^7小的数,要求的算法是O(n)（给了提示..说往 N 进制那方面想）
空间换时间，开一个N^7大的数组，有数的位置就标记，然后遍历一遍
复杂度是？
用基数排序 对每位排序
基数排序已经可以 O(n)了,准备 10个 vector<int>,从最低位数字开始,
放入相应的桶里,然后再顺序取出来, 然后再从次低位放入相应桶里, 在顺序取出来
*/
#include<iostream>
#include<string>
#include<queue>
#include<vector>
using namespace std;
size_t n; //n个数
size_t maxLen=0; //最大的数字位数
vector< queue<string> > vec(10); //10个桶
vector<string>result;
void sort()
{
for(size_t i=0;i<maxLen;++i) //最大的数字位数
{
for(size_t j=0;j<result.size();++j) //n个数
{
if(i>=result[j].length())
vec[0].push(result[j]);
else
vec[ result[j][result[j].length()-1-i]-'0' ].push(result[j]);
}
result.clear();
for(size_t k=0;k<vec.size();++k)
{
while(!vec[k].empty())
{
result.push_back(vec[k].front());
vec[k].pop();
}
}
}
}
int main()
{
cin>>n;
string input;
for(size_t i=0;i<n;++i)
{
cin>>input;
result.push_back(input);
if(maxLen==0||input.length()>maxLen)
maxLen=input.length();
}
sort();
for(size_t i=0;i<n;++i)
cout<<result[i]<<" ";
cout<<endl;
return 0;
}
/*
5
4 10 7 123 33
*/