c++歸并排序詳解

說一說歸并排序

創(chuàng)新互聯(lián)建站專注于企業(yè)全網整合營銷推廣、網站重做改版、沾化網站定制設計、自適應品牌網站建設、html5、商城開發(fā)、集團公司官網建設、外貿網站制作、高端網站制作、響應式網頁設計等建站業(yè)務，價格優(yōu)惠性價比高，為沾化等各大城市提供網站開發(fā)制作服務。

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

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

 c++歸并排序詳解

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

 void merge(int arr[],int l,int mid,int r)
 {
   int aux[r-l+1];//開辟一個新的數(shù)組，將原數(shù)組映射進去 
   for(int m=l;m<=r;m++)
   {
     aux[m-l]=arr[m];
   }
   
   int i=l,j=mid+1;//i和j分別指向兩個子數(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++;
         }
   } 
 }

上圖代碼已經完成了歸并中的“并”這一部分，歸并歸并，有并必有歸，如下實現(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不方便使用者調用，于是我們創(chuàng)建一個方便自己調用的my_merge_sort函數(shù)

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

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

 #include <iostream>
 using namespace std;
 
 
 void merge(int arr[],int l,int mid,int r)
 {
   int aux[r-l+1];//開辟一個新的數(shù)組，將原數(shù)組映射進去 
   for(int m=l;m<=r;m++)
   {
     aux[m-l]=arr[m];
   }
   
   int i=l,j=mid+1;//i和j分別指向兩個子數(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++;
         }
   } 
 } 
 //遞歸的使用歸并排序，對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;
 }

上面實現(xiàn)的歸并排序是自頂向下的，我們可以以另外一種方向來實現(xiàn)歸并，改遞歸為迭代。如下實現(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];//開辟一個新的數(shù)組，將原數(shù)組映射進去 
   for(int m=l;m<=r;m++)
   {
     aux[m-l]=arr[m];
   }
   
   int i=l,j=mid+1;//i和j分別指向兩個子數(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防止越界 
     {//對arr[i...sz-1]和arr[i+sz.....i+2*sz-1]進行排序 
       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;  
 }

網頁標題：c++歸并排序詳解
本文URL：http://bm7419.com/article0/phdcoo.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供App開發(fā)、標簽優(yōu)化、網站制作、面包屑導航、網站營銷、企業(yè)建站

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)

h5響應式網站建設