溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

c++歸并排序詳解

發(fā)布時(shí)間：2020-10-07 01:09:29 來(lái)源：腳本之家 閱讀：200 作者：傻蝸牛 欄目：編程語(yǔ)言

說(shuō)一說(shuō)歸并排序

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

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

 c++歸并排序詳解

如圖，從下到上，每一步都需要將兩個(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)的歸并排序是自頂向下的，我們可以以另外一種方向來(lái)實(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;  
 }
向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手