对于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);                                        }                     }

评论