基数排序
一位一位进行排序，这里的板子中，\(p\)代表模数，可以自行选择
\(C++ Code:\)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 100005
using namespace std;
#define p 128
int n,a[N],ot[N],t[p];
template<typename T>
void RadixSort(T *a,int l,int r)
{
T mx=a[l];
for (int i=l+1;i<=r;i++)
if (a[i]>mx)
mx=a[i];
int ws=0;
while (mx)
{
ws++;
mx/=p;
}
for (int i=1,g=1;i<=ws;i++)
{
memset(t,0,sizeof(t));
for (int j=l;j<=r;j++)
t[(a[j] / g) % p]++;
for (int j=1;j<p;j++)
t[j]+=t[j-1];
for (int j=r;j>=l;j--)
ot[t[(a[j] / g) % p]--]=a[j];
memcpy(a+l,ot+1,(r-l+1)*sizeof(T));
g*=p;
}
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
RadixSort(a,1,n);
for (int i=1;i<=n;i++)
printf("%d ",a[i]);
putchar('\n');
return 0;
}