正文

排序方法2006-01-13 15:33:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/love0you0forever/9550.html

分享到:

    对于n个元素的数组的排序,最佳算法的运行时间是O(nlog2n)≈p*nlog2n。方法有堆排序与快速排序。

  (1)堆排序

    方法SORT重排一个数组,而方法SORT2用于同时对另一组作相应重排。(用java语言)

      1,方法SORT。

 public class love

       {

           void sort(int n,double ra[])

                {

                        int i,j,l,ir;

                       double rra;

                      l=(int)(n/2)+1;

                     ir=n;

                     do

                        {if(l>1)

                           {

                               l=l-1;

                                rra=ra[l];

                             }

                       else

                           {

                                rra=ra[ir];

                                ra[ir]=ra[l];

                                ir=ir-1;

                                 if(ir==1)

                                    {

                                          ra[1]-rra;

                                          return;

                                        }

                              }

                i=l;

                 j=l+1;

                while(j<=ir)

                     {

                          if(j

                              {

                                  if(ra[j]

                                       {

                                           j+=1;

                                         }

                                 }

                          if(rra

                              {

                                   ra[i]ra[j];

                                   i=j;

                                   j+=j;

                                  }

                           else

                                {

                                    j=ir+1;

                               }

                          }

                         ra[i]=rra;

                     }while(true);

              }

         }

       2.SORT2.

   public class meng

    {

        void sort2(int n,double ra[],double rb[])

            {

                  int l,ir,i,j;

                   double rra,rrb;

                   l=n/2+1;

                   ir=n;

                    do

                       {

                             if(l>1)

                                 {

                                      l=l-1;

                                       rra=ra[l];

                                        rrb=rb[l];

                                      }

                                 else

                                     {

                                         rra=ra[ir];

                                          rra=rb[ir];

                                           ra[ir]=ra[l];

                                           ir=ir-1;

                                            if(ir==1)

                                                 {

                                                      ra[1]=rra;

                                                      rb[1]=rrb;

                                                       return;

                                                   }

                                        }

                                     i=l;

                                      j=l+1;

                                      while(j<=ir)

                                          {

                                               if(j<=ir)

                                                   {

                                                       if(j

                                                           {

                                                                if(ra[j]

                                                                     {

                                                                          j=j+1;

                                                                        }

                                                            }

                                                       if(rra

                                                            {

                                                                 ra[i]=ra[j];

                                                                  rb[i]=rb[j];

                                                                   i=j;

                                                                    j=j+1;

                                                                }

                                                              else

                                                                {

                                                                     j=ir+1;

                                                                  }

                                                }

                                     }

                               ra[i]=rra;

                                rb[i]=rrb;

                              }while(true);

                     }

          }

  2.快速排序

           使用说明

                QCKSRT(N,ARR[])

                 N      整形变量,输入参数,待排序数组长度

                  ARR[]  N个元数的一维实型数组,输入、输出参数,输入时存放待排序的数组,输出时存放排序后的结果

             方法QCKSRT.

                public class  chen

                   {

                         void qcksrt(int n,double arr[])

                             {

                                 int m=7; int nstack=50;int fm=7875;int fa=211;

                                     int fc=1663; double a,fmi=0.00012698413;

                                 int istack[]=new int[51];

                                  int jstack=0;

                                  int i,j,iq,l=1;

                                     boolrean done=true;

                                    int ir=n;

                                     int fx=0;

                                      do

                                          {

                                               if(ir-l

                                                   {

                                                       for(j=l+1;j

                                                            {

                                                                 a=arr[j];

                                                                  for(i=j-1;i>=1;i--)

                                                                       {

                                                                           if(arr[i]<=a)

                                                                              {

                                                                                  break;

                                                                               }

                                                                            arr[i+1]=arr[i];

                                                                        }

                                                                       if(arr[i]==0)

                                                                          {

                                                                               i=0;

                                                                            }

                                                                        arr[i+1]=a;

                                                                     }

                                                                    if(jstack==0)

                                                                        {

                                                                              return;

                                                                           }

                                                                         ir=istack[jstack];

                                                                         l=istack[jstack-1];

                                                                          jstack=jstack-2;

                                                                       }

                                                                 else

                                                                    {

                                                                         i=l;

                                                                          j=ir;

                                                                          fx=fx*fa+fc-fm*(int)((fx*fa+fc)/fm);

                                                                          iq=(int)(l+(ir-l+1)*(fx*fm);

                                                                           a=arr[iq];

                                                                           arr[iq]=arr[l];

                                                                             do

                                                                               {

                                                                                    do

                                                                                        {

                                                                                            if(j>0)

                                                                                              {

                                                                                                 if(a

                                                                                                    {

                                                                                                       j=j-1;

                                                                                                        done=false;

                                                                                                      }

                                                                                                   else

                                                                                                     {

                                                                                                        done=true;

                                                                                                       }

                                                                                                 }

                                                                                           }while(!done)

                                                                                             if(j<=i)

                                                                                               {

                                                                                                  arr[i]=a;

                                                                                                   break;

                                                                                                }

                                                                                              arr[i]=arr[j];

                                                                                               i=i+1;

                                                                                                do

                                                                                                   {

                                                                                                      if(i

                                                                                                        {

                                                                                                            if(a>arr[i])

                                                                                                               {

                                                                                                                   i=i+1;

                                                                                                                    done=false;

                                                                                                                  }

                                                                                                               else

                                                                                                                 {

                                                                                                                      done=true;

                                                                                                                   }

                                                                                                             }

                                                                                                }while(!done);

                                                                                                 if(j<=i)

                                                                                                    {

                                                                                                        arr[j]=a;

                                                                                                         i=j;

                                                                                                        break;

                                                                                                      }

                                                                                                 arr[j]=arr[i];

                                                                                                  j=j-1;

                                                                                         }while(true);

                                                                                        jstack=jstack+2;

                                                                                         if(jstack>nstack)

                                                                                            {

                                                                                                Sytem.out.println("nstack must be made larger.");

                                                                                            }

                                                                                        if(ir-i>=i-l)

                                                                                           {

                                                                                               istack[jstack]=ir;

                                                                                                istack[jstack-1]=l;

                                                                                                l=l+1;

                                                                                            }

                                                                             }

                                                             }while(true);

                                       }

                    }

阅读(3273) | 评论(0)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

暂无评论
您需要登录后才能评论,请 登录 或者 注册