考试现场yy

和SA的基数排序一样啦。甚至更简单的多。

从低到高按位处理。

每次重新更新。

也可以写成SA的形式：甚至我直接用的SA数组名

luogu【模板】快速排序

// luogu-judger-enable-o2#include
     
      #define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=100002;int a[N];int b[N];int buc[N],m;int x[N],y[N];int sa[N],rk[N];void ji(int n){    m=10;    ll tmp=10;    int num;    for(reg i=1;i<=n;++i) ++buc[x[i]=a[i]%10];    for(reg i=0;i<=m;++i) buc[i]+=buc[i-1];    for(reg i=1;i<=n;++i) sa[buc[x[i]]--]=i;    for(reg k=2;k<=10;++k){        //cout<<" kk "<
      
       <
       
        =1;--i) sa[buc[x[y[i]]]--]=y[i];        num=1;        for(reg i=2;i<=n;++i){            if(a[sa[i]]%tmp!=a[sa[i-1]]%tmp) ++num;        }        //if(num==n) break;        m=num;    }    for(reg i=1;i<=n;++i) b[i]=a[sa[i]];}int main(){    int n;    cin>>n;    for(reg i=1;i<=n;++i) rd(a[i]);    ji(n);    for(reg i=1;i<=n;++i){        printf("%d ",b[i]);    }return 0;}}signed main(){//    freopen("data.in","r",stdin);//    freopen("my.out","w",stdout);    Miracle::main();    return 0;}/*   Author: *Miracle*   Date: 2019/1/14 9:24:07*/
       
      
     

复杂度O(nlogmax)log是以10为底的。值域小的时候理论比sort快。

 

 

当然不必这么拘束

基数排序就是分块的桶排

所以可以以2^8为基数，也就是2^8的桶

4次就搞定了

（2^8对缓存有利，，，有利于卡常）