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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

几种比较  

2008-07-17 16:26:49|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

几种排序的比较

待测评的排序:

选择排序

堆排序

快排

 

 

我编的程序:

选排(输入:datain.txt 输出:dataout2.txt)

#include <ctime>

#include <conio.h>

using namespace std;

int main()

{

    int t1;

    t1=clock();

    FILE *fin;

    FILE *fout;

    fin=fopen("datain.txt","r");

    fout=fopen("dataout2.txt","w");

    int i,j,k,n;

    int maxid,max;

    int datas[500000];

    fscanf(fin,"%d\n",&n);

    for (i=0;i<n;i++)

    {

        fscanf(fin,"%d ",datas+i);

    }

    for (i=0;i<n-1;i++)

    {

        max=datas[i];

        maxid=i;

        for (j=i+1;j<n;j++)

        {

            if (datas[j]<max)

            {

               max=datas[j];

               maxid=j;

            }

        }

        k=datas[i];

        datas[i]=datas[maxid];

        datas[maxid]=k;

    }

    for (i=0;i<n;i++)

    {

        fprintf(fout,"%d ",datas[i]);

    }

    fprintf(fout,"\n");fclose(fout);

    fclose(fin);

    printf("%d\n",clock()-t1);

    getch();

    return 0;

}

 

快排(输入:datain.txt 输出:dataout.txt)

 

 

#include <cstdio>

#include <ctime>

#include <conio.h>

#define NumBer 500000

using namespace std;

int datas[NumBer];

int qs(int b,int e)

{

    if (b>=e)return 0;

    int i,j,k;

    j=b;

    for (i=b;i<=e;i++)

    {

        if (datas[i]<datas[j])

        {

           k=datas[i];

           datas[i]=datas[j+1];

           datas[j+1]=k;

           k=datas[j];

           datas[j]=datas[j+1];

           datas[j+1]=k;

           j++;

        }

    }

    if (j==e)qs(b,e-1);

    else

    {

        qs(b,j);

        qs(j+1,e);

    }

    return 0;

}

int main()

{

    int t1,n,i,j,k;

    t1=clock();

    FILE *fin;

    FILE *fout;

    fin=fopen("datain.txt","r");

    fout=fopen("dataout3.txt","w");

    fscanf(fin,"%d\n",&n);

    for (i=0;i<n;i++)fscanf(fin,"%d ",datas+i);

    qs(0,n-1);

    for (i=0;i<n;i++)fprintf(fout,"%d ",datas[i]);

    fclose(fin);

    fclose(fout);

    printf("%d\n",clock()-t1);

    getch();

    return 0;

}

 

 

堆排序(输入:datain.txt 输出:dataout.txt)

 

#include <stdio.h>

#include <conio.h>

#include <ctime>

#define NumBer 500000

using namespace std;

int N;

int datas[NumBer+1];

int lc[NumBer+1];

int rc[NumBer+1];

int godown(int id)

{

    int i=id;

    int j,k,l;

    while (i<N)

    {

          j=lc[i];

          k=rc[i];

          if (j>=N)j=-1;else j=datas[j];

          if (k>=N)k=-1;else k=datas[k];

          if (datas[i]<j || datas[i]<k)

          {

             if (j>k)

             {

                l=datas[i];

                datas[i]=datas[lc[i]];

                datas[lc[i]]=l;

                i=lc[i];

             }

             else

             {

                 l=datas[i];

                 datas[i]=datas[rc[i]];

                 datas[rc[i]]=l;

                 i=rc[i];

             }

          }

          else

          {

              break;

          }

    }

    return 0;

}

int formating()

{

    int i,j,k,p1,p2;

    int dui[NumBer+1];

    j=k=0;

    j++;

    dui[0]=0;

    p1=0;p2=1;

    k=1;

    while (k>0 && k<=N)

    {

          k--;

          i=dui[p1];

          p1++;p1%=N;

          lc[i]=j++;

          rc[i]=j++;

          if (lc[i]<N)

          {

             dui[p2++]=lc[i];

             p2%=N;

             k++;

          }

          if (rc[i]<N)

          {

             dui[p2++]=rc[i];

             p2%=N;

             k++;

          }

    }

    return 0;

}

int makebigheap()

{

    int i,j,k;

    for (i=N-1;i>=0;i--)

    {

        //puts("pause");getch();

        godown(i);

        //puts("pause2");getch();

    }

    return 0;

}

int main()

{

    int p1;

    p1=clock();

    FILE *fin;

    FILE *fout;

    if (fin==0 || fout==0){return 0;}

    fin=fopen("datain.txt","r");

    fout=fopen("dataout.txt","w");

    fscanf(fin,"%d\n",&N);

    int i,j,k;

    int n;

    for (i=0;i<N;i++)

    {

        fscanf(fin,"%d ",datas+i);

    }

    n=N;

    formating();

    makebigheap();

    for (i=N-1;i>=0;i--)

    {

        j=datas[0];

        datas[0]=datas[i];

        datas[i]=j;

        N--;

        godown(0);

    }

    for (i=0;i<n;i++)

    {

        fprintf(fout,"%d ",datas[i]);

    }

    fprintf(fout,"\n");

    printf("%d\n",clock()-p1);

    getch();

    fclose(fin);

    fclose(fout);

    return 0;

}

输入文件第一行为数据个数,以下为各个数据

 

每个程序输出文件,屏幕输出运行时间(毫秒)

我无私赠送三个程序500000、100000、50000、10000、5000个随机数

结果如下

         500000          100000  50000   10000  5000

快排:1882             343        171       62        31

堆排:3312             500        218       62        31

选择排序:600180  22266    5513     243      93

 

看来,快排在随机数据上表现出色!

堆排在理论上十分出色,不过实现起来比较不理想;

选择排序遇到大数据,就......

  评论这张
 
阅读(451)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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