c++歸并排序詳解

更新時(shí)間：2017年05月30日 12:40:16 作者：傻蝸牛

歸并排序遵循分治法的思想：將原問題分解為幾個(gè)規(guī)模較小但類似于原問題的子問題，遞歸地求解這些子問題，然后再合并這些子問題的解來建立原問題的解。分治模式在每層遞歸時(shí)都有三個(gè)步驟：分解、解決、合并。歸并排序完全遵循該模式。

說一說歸并排序

歸并排序：歸并排序（英語(yǔ)：Merge sort，或mergesort），是創(chuàng)建在歸并操作上的一種有效的排序算法，效率為O(n log n)。1945年由約翰·馮·諾伊曼首次提出。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用，且各層分治遞歸可以同時(shí)進(jìn)行。

歸并排序的核心思想是將兩個(gè)有序的數(shù)列合并成一個(gè)大的有序的序列。通過遞歸，層層合并，即為歸并。

如圖，從下到上，每一步都需要將兩個(gè)已經(jīng)有序的子數(shù)組合并成一個(gè)大的有序數(shù)組，如下是實(shí)現(xiàn)合并的具體代碼，請(qǐng)讀者細(xì)細(xì)體會(huì)

 void merge(int arr[],int l,int mid,int r)
 {
   int aux[r-l+1];//開辟一個(gè)新的數(shù)組，將原數(shù)組映射進(jìn)去 
   for(int m=l;m<=r;m++)
   {
     aux[m-l]=arr[m];
   }
   
   int i=l,j=mid+1;//i和j分別指向兩個(gè)子數(shù)組開頭部分
   
   for(int k=l;k<=r;k++)
   {
     if(i>mid)
     {
       arr[k]=aux[j-l];
       j++;
     }
     else if(j>r)
     {
       arr[k]=aux[i-l];
       i++;
     }
         else if(aux[i-l]<aux[j-l])
         {
           arr[k]=aux[i-l];
           i++;  
         }
         else
         {
           arr[k]=aux[j-l];
           j++;
         }
   } 
 }

上圖代碼已經(jīng)完成了歸并中的“并”這一部分，歸并歸并，有并必有歸，如下實(shí)現(xiàn)“歸”的部分

 void merge_sort(int arr[],int l,int r)
{
  if(l >=r)
    return ;
  int mid=(l+r)/2; 
  merge_sort(arr,l,mid);
  merge_sort(arr,mid+1,r);
  merge(arr,l,mid,r);
}

由于上圖中的l，r不方便使用者調(diào)用，于是我們創(chuàng)建一個(gè)方便自己調(diào)用的my_merge_sort函數(shù)

 void my_merge_sort(int arr[],int n)
{
  merge_sort(arr,0,n-1);  
}

以上我們便實(shí)現(xiàn)了歸并排序中的歸和并，歸并排序是利用二分法實(shí)現(xiàn)的排序算法，時(shí)間復(fù)雜度為nlogn，是一種比較快速的排序算法。如下是筆者自己寫的歸并排序的全部代碼，

 #include <iostream>
 using namespace std;
 
 
 void merge(int arr[],int l,int mid,int r)
 {
   int aux[r-l+1];//開辟一個(gè)新的數(shù)組，將原數(shù)組映射進(jìn)去 
   for(int m=l;m<=r;m++)
   {
     aux[m-l]=arr[m];
   }
   
   int i=l,j=mid+1;//i和j分別指向兩個(gè)子數(shù)組開頭部分
   
   for(int k=l;k<=r;k++)
   {
     if(i>mid)
     {
       arr[k]=aux[j-l];
       j++;
     }
     else if(j>r)
     {
       arr[k]=aux[i-l];
       i++;
     }
         else if(aux[i-l]<aux[j-l])
         {
           arr[k]=aux[i-l];
           i++;  
         }
         else
         {
           arr[k]=aux[j-l];
           j++;
         }
   } 
 } 
 //遞歸的使用歸并排序，對(duì)arr[l....r]排序 
 void merge_sort(int arr[],int l,int r)
 {
   if(l >=r)
     return ;
   int mid=(l+r)/2; 
   merge_sort(arr,l,mid);
   merge_sort(arr,mid+1,r);
   merge(arr,l,mid,r);
 }
 
 void my_merge_sort(int arr[],int n)
 {
   merge_sort(arr,0,n-1);  
 } 
 
 int main()
 {
   int a[6];
   for(int i=0;i<6;i++)
   {
     cin>>a[i];
   }
   my_merge_sort(a,6);
   for(int i=0;i<6;i++)
   {
     cout<<a[i]<<" ";
   }
   return 0;
 }

上面實(shí)現(xiàn)的歸并排序是自頂向下的，我們可以以另外一種方向來實(shí)現(xiàn)歸并，改遞歸為迭代。如下實(shí)現(xiàn)

 #include <iostream>
 #include <math.h> 
 using namespace std;
 
 void merge(int arr[],int l,int mid,int r)
 {
   int aux[r-l+1];//開辟一個(gè)新的數(shù)組，將原數(shù)組映射進(jìn)去 
   for(int m=l;m<=r;m++)
   {
     aux[m-l]=arr[m];
   }
   
   int i=l,j=mid+1;//i和j分別指向兩個(gè)子數(shù)組開頭部分
   
   for(int k=l;k<=r;k++)
   {
     if(i>mid)
     {
       arr[k]=aux[j-l];
       j++;
     }
     else if(j>r)
     {
       arr[k]=aux[i-l];
       i++;
     }
         else if(aux[i-l]<aux[j-l])
         {
           arr[k]=aux[i-l];
           i++;  
         }
         else
         {
           arr[k]=aux[j-l];
           j++;
         }
   } 
 }
 
 void mergesort(int arr[],int n)
 {
   for(int sz=1;sz<=n;sz+=sz)
   {
     for(int i=0;i+sz<n;i+=sz+sz)//i+sz防止越界 
     {//對(duì)arr[i...sz-1]和arr[i+sz.....i+2*sz-1]進(jìn)行排序 
       merge(arr,i,i+sz-1,min(i+sz+sz-1,n-1));  //min函數(shù)防止越界 
     } 
   } 
   
 } 
 
 int main()
 {
   int a[5];
   for(int i=0;i<5;i++)
   {
     cin>>a[i];
   }
   mergesort(a,5);
   for(int i=0;i<5;i++)
   {
     cout<<a[i]<<" ";
   }
   return 0;  
 }

您可能感興趣的文章: