wizen-coder
10/4/2018 - 10:07 AM

## 合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将

``````//2d7-1 递归实现二路归并排序(递归实现的合并排序)
#include "stdafx.h"
#include <iostream>
using namespace std;

int a[] = {10,5,9,4,3,7,8};
int b[7];

template <class Type>
void Merge(Type c[],Type d[],int l,int m,int r);

template <class Type>
void MergeSort(Type a[],int left,int right);

int main()
{
for(int i=0; i<7; i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
MergeSort(a,0,6);
for(int i=0; i<7; i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}

template <class Type>
void Merge(Type c[],Type d[],int l,int m,int r)
{
int i = l,j = m + 1,k = l;
while((i<=m)&&(j<=r))
{
if(c[i]<=c[j])
{
d[k++] = c[i++];
}
else
{
d[k++] = c[j++];
}
}

if(i>m)
{
for(int q=j; q<=r; q++)
{
d[k++] = c[q];
}
}
else
{
for(int q=i; q<=m; q++)
{
d[k++] = c[q];
}
}
}

template <class Type>
void MergeSort(Type a[],int left,int right)
{
if(left<right)
{
int i = (left + right)/2;
MergeSort(a,left,i);
MergeSort(a,i+1,right);
Merge(a,b,left,i,right);//合并到数组b

//复制回数组a
for(int g=left; g<=right; g++)
{
a[g] = b[g];
}
}
}
``````
``````//2d7-1 自然二路归并排序(合并排序非递归实现)
#include "stdafx.h"
#include <iostream>
using namespace std;

int a[] = {10,5,9,4,3,7,8};
int b[7];

template <class Type>
void Merge(Type c[],Type d[],int l,int m,int r);

template <class Type>
void MergePass(Type x[],Type y[],int s,int n);

template <class Type>
void MergeSort(Type a[],int n);

int main()
{
for(int i=0; i<7; i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
MergeSort(a,7);
for(int i=0; i<7; i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}

template <class Type>
void Merge(Type c[],Type d[],int l,int m,int r)
{
int i = l,j = m + 1,k = l;
while((i<=m)&&(j<=r))
{
if(c[i]<=c[j])
{
d[k++] = c[i++];
}
else
{
d[k++] = c[j++];
}
}

if(i>m)
{
for(int q=j; q<=r; q++)
{
d[k++] = c[q];
}
}
else
{
for(int q=i; q<=m; q++)
{
d[k++] = c[q];
}
}
}

template <class Type>
//合并大小为s的相邻子数组
void MergePass(Type x[],Type y[],int s,int n)
{
int i = 0;
while(i<=n-2*s)
{
//合并大小为s的相邻两段子数组
Merge(x,y,i,i+s-1,i+2*s-1);
i = i + 2*s;
}
//剩下的元素个数少于2s
if(i+s<n)
{
Merge(x,y,i,i+s-1,n-1);
}
else
{
for(int j=i; j<=n-1; j++)
{
y[j]=x[j];
}
}
}

template <class Type>
void MergeSort(Type a[],int n)
{
Type *b = new Type[n];
int s = 1;
while(s<n)
{
MergePass(a,b,s,n);//合并到数组b
s += s;
MergePass(b,a,s,n);//合并到数组a
s += s;
}
}
``````