q_and_m.cpp

归并和快速算法比较

#include "Q_and_M.h"
//---------------------------------------------------------------------------
void Merge(int A[], int T[], int low, int mid, int high)
{
 int i=low;
 int j=mid+1;
 int p=low;
 while((i<=mid)&&(j<=high))
      {
       if( A[i]<=A[j] )
         {
           T[p]=A[i];
           i++;
         }//emd if
       else
         {
           T[p]=A[j];
           j++;
         }//end else
       p++;
      }//end while
 while( i<=mid )
      {
        T[p]=A[i];
        i++;
        p++;
      }//end while
 while( j<=high )
      {
        T[p]=A[j];
        j++;
        p++;
      }//end while
}
//---------------------------------------------------------------------------
void MergePass(int A[], int T[],int length, int n)
{
 int low=1;
 while((low+2*length-1) <= n)
      {
        Merge(A, T, low, low+length-1, low+2*length-1);
        low=low+2*length;
      }//end while
 if( low+length-1 <=n )//记录数为length与记录数小于length的合并
    Merge(A, T, low, low+length-1, n);
 else //直接复制记录数小于或等于length的最后一个子序列
    for(int j=low; j<=n; j++ )
        T[j]=A[j];
}
//---------------------------------------------------------------------------
void MergeSort(int A[], int n)
{
  int length=1;
  int *T;
  T=new int [n+1];
  while( length < n )
       {
        MergePass(A, T, length, n);
        length=2*length;
        MergePass(T, A, length, n);
        length=2*length;
       }//end while
}
//===========================================================================
void MergeR(int A[], int T[], int low, int mid, int high)
{
 int i=low;
 int j=mid+1;
 int p=low;
 while((i<=mid)&&(j<=high))
      {
       if( A[i]<=A[j] )
         {
           T[p]=A[i];
           i++;
         }//emd if
       else
         {
           T[p]=A[j];
           j++;
         }//end else
       p++;
      }//end while
 while( i<=mid )
      {
        T[p]=A[i];
        i++;
        p++;
      }//end while
 while( j<=high )
      {
        T[p]=A[j];
        j++;
        p++;
      }//end while
 for(int i=low;i<=high;i++)
     A[i]=T[i];
}
//---------------------------------------------------------------------------
void MergeSortR(int A[], int T[], int low, int high)
{
 if( low<high )
   {
    int mid=(low+high)/2;
    MergeSortR(A, T, low, mid);
    MergeSortR(A, T, mid+1, high);
    MergeR(A, T, low, mid, high);
   }
}
//===========================================================================
int Split(int A[], int low, int high)
{
 A[0]=A[low];
 int i=low;
 for( int j=low+1; j<=high; j++ )
    {
      if( A[j]<=A[0] )
        {
          i++;
          if( i!=j )
            {
              int t=A[j];
              A[j]=A[i];
              A[i]=t;
            }//end if
        }//end if
    }//end for
 int t=A[i];
 A[i]=A[low];
 A[low]=t;
 return i;
}
//---------------------------------------------------------------------------
void QuickSort(int A[], int low, int high)
{
 if( low < high )
   {
     A[0]=A[low];
     if( A[low] > A[(low+high)/2] )
       {
         A[low]=A[(low+high)/2];
         A[(low+high)/2]=A[0];
       }//end if
     else   A[0]=A[(low+high)/2];
     if( A[(low+high)/2] > A[high] )
       {
         A[(low+high)/2]=A[high];
         A[high]=A[0];
       }//end if
    A[0]=A[low];
    A[low]=A[(low+high)/2];
    A[(low+high)/2]=A[0];
    int Vmid=Split(A,low,high);
    QuickSort(A,low,Vmid-1);
    QuickSort(A,Vmid+1,high);
   }//end if
}
//---------------------------------------------------------------------------