注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

排序测评  

2009-03-08 14:48:04|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
void ss1(int *d,int N){int t;
     if (N>20000)return;
    for (int i=0;i<N;i++)for (int j=i;j<N;j++)if (d[i]>d[j]){
        t=d[i];d[i]=d[j];d[j]=t;
    }
}
void ss2(int *d,int N){int t,j;
     if (N>20000)return;
    for (int i=1;i<N;i++){
        t=d[i];
        for (j=i-1;j>=0 && d[j]>t;j--)d[j+1]=d[j];
        d[j+1]=t;
    }
}
void ss3(int *d,int N){int min,t;
     if (N>20000)return;
    for (int i=0;i<N;i++){
        for (int j=min=i;j<N;j++)
            if (d[j]<d[min])min=j;
        t=d[i];d[i]=d[min];d[min]=t;
    }
}
void qs1(int b,int e,int *d){int i=b,j,t;if (b>=e)return;
    for (j=b+1;j<=e;j++)if (d[j]<d[i]){
        t=d[j];d[j]=d[i+1];d[i+1]=t;
        t=d[i];d[i]=d[i+1];d[i+1]=t;
        i++;
    }
    qs1(b,i-1,d);qs1(i+1,e,d);
}
void qs1(int *d,int n){qs1(0,n-1,d);}
void qs2(int b,int e,int *d){if (b>=e)return;int i,t;
     for (int j=i=b+1;j<=e;j++)if (d[j]<d[b])
         {t=d[j];d[j]=d[i];d[i]=t;i++;}
     i--;
     t=d[b];d[b]=d[i];d[i]=t;
     qs2(b,i-1,d);qs2(i+1,e,d);
}
void qs2(int *d,int n){qs2(0,n-1,d);}
void qs3(int b,int e,int *d){int i=b,j,t;if (b>=e)return;
    t=d[b];d[b]=d[(b+e)/2];d[(b+e)/2]=t;
    for (j=b+1;j<=e;j++)if (d[j]<d[i]){
        t=d[j];d[j]=d[i+1];d[i+1]=t;
        t=d[i];d[i]=d[i+1];d[i+1]=t;
        i++;
    }
    qs3(b,i-1,d);qs3(i+1,e,d);
}
void qs3(int *d,int n){qs3(0,n-1,d);}
void qs4(int b,int e,int *d){if (b>=e)return;int i,t;
     t=d[b];d[b]=d[(b+e)/2];d[(b+e)/2]=t;
     for (int j=i=b+1;j<=e;j++)if (d[j]<d[b])
         {t=d[j];d[j]=d[i];d[i]=t;i++;}
     i--;
     t=d[b];d[b]=d[i];d[i]=t;
     qs4(b,i-1,d);qs4(i+1,e,d);
}
void qs4(int *d,int n){qs4(0,n-1,d);}
int *tmp;
void ms(int b,int e,int *d){if (b>=e)return;int x,y;
    ms(b,(b+e)/2,d);
    ms((b+e)/2+1,e,d);
    for (int i=b;i<=e;i++)tmp[i]=d[i];
    x=b;y=(b+e)/2+1;
    while (x<=(b+e)/2 || y<=e){
          if (y>e || (x<=(b+e)/2 && tmp[x]<tmp[y])){
             d[x+y-(b+e)/2-1]=tmp[x];x++;
          }else{
             d[x+y-(b+e)/2-1]=tmp[y];y++;
          }
    }
}
void ms(int *d,int n){
     tmp=new int[n];
     ms(0,n-1,d);
     delete []tmp;
}
int *heap,N;
void go_down(int i){int max,t;max=i;
    if (2*i+1<N)if (heap[2*i+1]>heap[max])max=2*i+1;
    if (2*i+2<N)if (heap[2*i+2]>heap[max])max=2*i+2;
    if (max!=i){
       t=heap[max];heap[max]=heap[i];heap[i]=t;
       go_down(max);
    }
}
void hs(int *d,int n){int t;
    heap=d;N=n;
    for (int i=N-1;i>=0;i--)go_down(i);
    for (int i=N-1;i>0;i--){
        t=heap[0];heap[0]=heap[i];heap[i]=t;
        N--;go_down(0);
    }
}
void rs(int *d,int n){int *tmpa,*tmpb;
     tmpa=new int[65536];
     tmpb=new int[n];
     memset(tmpa,0,sizeof(int)*65536);
     for (int i=0;i<n;++i)++tmpa[(d[i]&65535)+1];
     for (int i=1;i<65536;++i)tmpa[i]+=tmpa[i-1];
     for (int i=0;i<n;++i)tmpb[tmpa[d[i]&65535]++]=d[i];
     memset(tmpa,0,sizeof(int)*65536);
     for (int i=0;i<n;++i)++tmpa[((tmpb[i]>>16)&65535)+1];
     for (int i=1;i<65536;++i)tmpa[i]+=tmpa[i-1];
     for (int i=0;i<n;++i)d[tmpa[(tmpb[i]>>16)&65535]++]=tmpb[i];
     delete []tmpa;
     delete []tmpb;
}
              1000     5000    10000    20000   100000   200000  1000000
      ss1        0      172      657       2656      failed      failed      failed
      ss2        0       62       250       953        failed      failed      failed
      ss3        0       78       313       1203      failed      failed      failed
      qs1        0        0        0           0            31          94          500
      qs2        0        0        0           15          31          63          359
      qs3        0        0        0           15          47          94          516
      qs4        0        0        0           16          31          78          375
       ms        0        0        0       16       47       94      562
       hs        0        0        0       16       46      125      891
       rs        0        0        0        0        0       31      157       best!
10000 1000000

排名:
1.radix sort
2.quick sort
6.merge sort
7.heap sort
8.insert sort
9.choose sort
10.swap sort
  评论这张
 
阅读(294)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017