c++歸並排序詳解。本站提示廣大學習愛好者：（c++歸並排序詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是c++歸並排序詳解正文
作者：傻蝸牛
歸並排序遵循分治法的思想：將原問題分解為幾個規模較小但類似於原問題的子問題，遞歸地求解這些子問題，然後再合並這些子問題的解來建立原問題的解。分治模式在每層遞歸時都有三個步驟：分解、解決、合並。歸並排序完全遵循該模式。說一說歸並排序
歸並排序：歸並排序（英語：Merge sort，或mergesort），是創建在歸並操作上的一種有效的排序算法，效率為O(n log n)。1945年由約翰·馮·諾伊曼首次提出。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞歸可以同時進行。
歸並排序的核心思想是將兩個有序的數列合並成一個大的有序的序列。通過遞歸，層層合並，即為歸並。
如圖，從下到上，每一步都需要將兩個已經有序的子數組合並成一個大的有序數組，如下是實現合並的具體代碼，請讀者細細體會
void merge(int arr[],int l,int mid,int r)
{
int aux[r-l+1];//開辟一個新的數組，將原數組映射進去
for(int m=l;m<=r;m++)
{
aux[m-l]=arr[m];
}
int i=l,j=mid+1;//i和j分別指向兩個子數組開頭部分
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 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不方便使用者調用，於是我們創建一個方便自己調用的my_merge_sort函數
void my_merge_sort(int arr[],int n)
{
merge_sort(arr,0,n-1);
}
以上我們便實現了歸並排序中的歸和並，歸並排序是利用二分法實現的排序算法，時間復雜度為nlogn，是一種比較快速的排序算法。如下是筆者自己寫的歸並排序的全部代碼，
#include <iostream>
using namespace std;
void merge(int arr[],int l,int mid,int r)
{
int aux[r-l+1];//開辟一個新的數組，將原數組映射進去
for(int m=l;m<=r;m++)
{
aux[m-l]=arr[m];
}
int i=l,j=mid+1;//i和j分別指向兩個子數組開頭部分
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;
}
上面實現的歸並排序是自頂向下的，我們可以以另外一種方向來實現歸並，改遞歸為迭代。如下實現
#include <iostream>
#include <math.h>
using namespace std;
void merge(int arr[],int l,int mid,int r)
{
int aux[r-l+1];//開辟一個新的數組，將原數組映射進去
for(int m=l;m<=r;m++)
{
aux[m-l]=arr[m];
}
int i=l,j=mid+1;//i和j分別指向兩個子數組開頭部分
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函數防止越界
}
}
}
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;
}
