162 3. 让你排序N个比N^7小的数,要求的算法是O(n)

/*
3. 让你排序N个比N^7小的数,要求的算法是O(n)（给了提示..说往 N 进制那方面想）

空间换时间，开一个N^7大的数组，有数的位置就标记，然后遍历一遍
复杂度是？

用基数排序 对每位排序 
基数排序已经可以 O(n)了,准备 10个 vector,从最低位数字开始,
放入相应的桶里,然后再顺序取出来, 然后再从次低位放入相应桶里, 在顺序取出来
*/
#include  
#include 
#include 
#include 
using namespace std; 
size_t  n;  //n个数 
size_t  maxLen=0;  //最大的数字位数 
vector > vec(10);  //10个桶 
vectorresult; 

void sort() 
{ 
  for(size_t i=0;i  { 
    for(size_t j=0;j    { 
      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    { 
      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  { 
    cin>>input; 
    result.push_back(input); 
    if(maxLen==0||input.length()>maxLen) 
      maxLen=input.length(); 
  } 
  sort(); 
  for(size_t i=0;i    cout  cout  return 0; 
}
/*
5
4 10 7 123 33
*/