排序算法——归并排序

归并排序

归并排序的思想：

归并排序的思想其实完全是分治法的思想的体现，它完全遵循分治法的模式。

这里有必要再重提下分治法的思想：

将原有的问题分解为几个规模较小的但类似于原问题的子问题，递归的求解这些子问题，然后再合并这些子问题的解来求得原问题的解。

现在来看看归并排序的操作：

1 将等待排序的含有 n 个元素的序列分解成各具有 n/2个元素的两个子序列 (n为奇数时，某个子序列比另一个会多一个元素 但不会影响结果)

2 使用归并排序递归的排序两个子序列 ( 说白了就是把开始已分解的两个子序列再各自往下分解 )

3 合并两个已经排好序的子序列

简单的例子：

我们有一个序列 6 5 3 1 8 7 2 4

1 我们将其分为两组 一组为 6 5 3 1  另一组为 8 7 2 4

2 对前面两组再进行分解 6 5  和 3 1     以及  8  7  和 2  4

3 各小组进行排序得到    5 6  和  1 3     以及 7  8  和 2  4

4  5 6 和 1  3两个小组进行合并 (比较并排序)   以及 7   8  和 2  4 两个小组进行合并 (比较并排序) 得到两个小组 1 3 5 6 和2 3 4 8

5 这两个小组再合并 (比较并排序)  得到最终解 1  2  3  4  5  6  7  8

代码实现：

<span style="font-size:18px;">#include<iostream>
using namespace std;
int array1[100]={0},array2[100]={0};//两个数组，用于记录分解后的两个子序列
void Merge(int a[],int p,int q,int r)
{
	int n1=q-p+1;
	int n2=r-q;
	int i,j;
	for(i=0;i<n1;i++)
		array1[i]=a[p+i];
	for(j=0;j<n2;j++)
		array2[j]=a[q+j+1];
	array1[n1]=9999;//9999是哨兵，起到终止比较的作用
	array2[n2]=9999;
	i=j=0;
	for(int k=p;k<=r;k++)//for循环用来合并两个子序列
	{
		if(array1[i]<=array2[j])
		{
			a[k]=array1[i];
			i+=1;
		}
		else
		{
			a[k]=array2[j];
			j+=1;
		}
	}
}
void Merge_Sort(int a[],int p,int r)
{
	if(p<r)
	{
		int q=(p+r)/2;
		Merge_Sort(a,p,q);//递归调用合并左侧的子序列
		Merge_Sort(a,q+1,r);//递归调用合并右侧的子序列
		Merge(a,p,q,r);//递归调用进行分解并合并
	}
}
int main()
{
	int a[8]={6,5,3,1,8,7,2,4};
	Merge_Sort(a,0,7);
	for(int i=0;i<8;i++)
		cout<<a[i]<<" ";
	return 0;
}
</span>