它的基本原理是桶排，不过大家想必知道桶排有多么吃内存....想要排32位的整数需要4GB的BUFFER....恐怖吧~所以只好以时间换空间~减少空间开销，多画一点时间了。基数排序其实就是多趟桶排。

什么是基数排序？基数大家都应该知道....比如说10进制的基数就是10。我们比较10进制的数是怎么比较的？肯定是先看最高位，然后向个位发展...基数排序和这个原理是一样的。不过我们比较喜欢选择用2的整数次幂作为基数~因为除以2的整数次幂的时候可以用位移~

OK。废话不多说。来说一下基2快排函数的思路（以下都是伪代码）。

我们假设函数入口传入了原数组src以及长度N。那么，肯定要开一个计数器（因为毕竟是基于桶排的嘛~） count，还有一个临时数组temp[N]。我们以2^8作为基数，排序32位整数为例。

for 4 次(i=0,1,2,3)
{
ZeroMemory(count); //显然是要清空计数器的
memcpy(temp,src,n*4)；//以后的操作都是对temp操作的，最后以temp为原拷贝回src去
For k=0 to N-1 
{
  ++count[(temp[k]>>(8*i))&0xFF];//在这里进行桶排
}

entry_point=0;//这个变量记录了每个计数器数据经过排列后在数组中的位置

for k = 0 to 256
{
_temp=count[k];
count[k]=entry_point; //把相应数据个数变成了相应数据在数组中的位置
entry_point+=_temp; //显然是要把BASE ENTRY_POINT推后的~
}

for k=0 To N
src[count[(temp[k]>>(8*i))&0xFF]++]=temp[k]; //这里有点难理解。这个语句的意思是根据数组中这个数字相应“位”（相当于10进制的个位、十位）的位置把这个数字拷贝回原数组中，这样就对这个“位”排过序了

}

#include<iostream>
using namespace std;

void sort(unsigned int* src,unsigned int n)
{
 unsigned int count[256];
 unsigned int* temp=new unsigned int[n];

 for(unsigned int i=0;i<4;i++)
 {
  memset(count,0,256*sizeof(unsigned int));

  memcpy(temp,src,n*sizeof(unsigned int));

  for(unsigned int k=0;k<n;k++)
  {
   ++count[(temp[k]>>(8*i))&0xFF];
  }

  unsigned int _pos=0;

  for(unsigned int j=0;j<256;j++)
  {
   unsigned int _temp=count[j];
   count[j]=_pos;
   _pos+=_temp;
  }

  for(unsigned int l=0;l<n;l++)
  {
   src[count[(temp[l]>>(8*i))&0xFF]++]=temp[l];
  }
 }

 delete[] temp;

}

int main()
{
 unsigned int g_n=0;
 cin>>g_n;
 unsigned int* buffer=new unsigned int[g_n];
 for(unsigned int i=0;i<g_n;i++)
 {
  cin>>buffer[i];
 }
 
 sort(buffer,g_n);
 cout<<"the answer is:"<<endl;
 for(unsigned int i=0;i<g_n;i++)
 {
  cout<<buffer[i]<<" ";
 }
 cout<<endl;
 return 1;
}