c++歸并排序詳解

說一說歸并排序

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

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

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

c++歸并排序詳解

如圖，從下到上，每一步都需要將兩個已經(jīng)有序的子數(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++;
         }
   } 
 }

上圖代碼已經(jīng)完成了歸并中的“并”這一部分，歸并歸并，有并必有歸，如下實現(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)建一個方便自己調(diào)用的my_merge_sort函數(shù)

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

以上我們便實現(xiàn)了歸并排序中的歸和并，歸并排序是利用二分法實現(xiàn)的排序算法，時間復(fù)雜度為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;  
 }

網(wǎng)頁標題：c++歸并排序詳解
本文URL：http://muchs.cn/article0/phdcoo.html

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

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

猜你還喜歡下面的內(nèi)容