我SB了。。。各位神牛WS我囧。。。。最近教一个同学排序于是就写了3个排序的基本算法。。我发现基数排序真是快的跟鬼一样。。。
快速排序：
#include <iostream>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=10000000;
using namespace std;
int A[maxn];
void sort(int l,int r)
{
if(r-l<2)return;
int h=l,x=A[l+rand()%(r-l+1)];
for(int i=l;i<=r;i++)if(A[i]<x){int t=A[i];A[i]=A[h];A[h]=t;h++;}
sort(l,h-1);sort(h+1,r);
}
int main()
{
int n;cin>>n;rep(i,n)scanf("%d",A+i);sort(0,n-1);
}堆排序：
#include <cstdio>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=10000000;
using namespace std;
int n,A[maxn];
inline int swap(int&a,int&b){a^=b^=a^=b;}
void Up(int i)
{
if(i/2&&A[i/2]>A[i])swap(A[i],A[i/2]),Up(i/2);
}
void Down(int i)
{
int p=i*2;if(p>n)return;
if(p+1<=n&&A[p+1]<A[p])++p;
if(A[i]>A[p])swap(A[i],A[p]),Down(p);
}
int main()
{
scanf("%d",&n);rep(i,n)scanf("%d",A+i+1),Up(i+1);
rep(i,n)swap(A[1],A[n–]),Down(1);
}基数排序（每4位）：
#include <algorithm>
#include <cstdio>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>2,maxn=1000000;
using namespace std;
int S0[maxn],S1[maxn],n,C[16]={};
int*A=S0,*B=S1;
int main()
{
scanf("%d",&n);rep(i,n)scanf("%d",A+i);
rep(x,4)
{
int d=x*4;rep(i,16)C[i]=0;
rep(i,n)C[(A[i]>>d)&15]++;rep(i,16)if(i)C[i]+=C[i-1];
for(int i=n-1;i>=0;i–)B[–C[(A[i]>>d)&15]]=A[i];
swap(A,B);
}
}无论从代码长度还是速度来说。。都是基数排序强。。囧啊。。