归并排序的介绍，包括归并排序的特点、原理和完整实现代码。

归并排序（Merge Sort）

把两个或多个有序的子序列合并为一个

2路归并：二合一

k路归并：k合一

归并排序特点

• 是稳定排序
• 可用于链式结构，且不需要附加存储空间，但递归实现时仍需要开辟相应的递归工作栈
• 空间复杂度：O（n）
• 时间复杂度：O（nlogn）

归并排序过程(原理)

1. 若low > high ，则将序列分从中间mid = (low + high)/2
2. 对左半部分【low，mid】递归地进行归并排序
3. 对右半部分【mid+1，high】递归地进行归并排序
4. 将左右两个有序子序列Merge为一个

完整代码实现

#include<iostream>
#include<string>

using namespace std;

/* 辅助数组B */
int n = 10;
int* B = (int*)malloc(n * sizeof(int)); //方式一
int* B2 = new int[n]; //方式二

/* 
	归并
	A[low...mid]和A[mid+1...high]各自有序，将两个部分归并
*/
void Merge(int A[],int low,int mid,int high)
{
	int i, j, k;
	for ( k = low; k <= high; k++)
	{
		B[k] = A[k];  //将A中所有元素复制到B中
	}
	for (i = low,j = mid+1,k = i;i<=mid&&j<=high; k++)
	{
		if (B[i] <= B[j]) {
			A[k] = B[i++];//将较小值复制到A中
		}
		else
		{
			A[k] = B[j++];
		}
	}
	while (i<=mid)
	{
		A[k++] = B[i++];
	}
	while (j <= high)
	{
		A[k++] = B[j++];
	}
}

/* 归并排序 */
void MergeSort(int A[],int low,int high) {
	if (low<high) {
		int mid = (low + high) / 2; //从中间划分
		MergeSort(A, low, mid);  //对左半部分归并排序
		MergeSort(A, mid+1, high); //右半部分归并排序
		Merge(A, low, mid, high); //归并
	}
}

int main()
{
	int a[] = { 3,5,2,6,1,4,9,8 };
	MergeSort(a, 0, 7);
	cout << "归并排序后：" << endl;
	for (int i = 0; i < 8; i++)
	{
		cout << a[i];
		if (i == 7)
		{
			cout <<endl;;
		}
		else
		{
			cout << ",";
		}
	}
	return 1;
}

运行结果：

归并排序后：
1,2,3,4,5,6,8,9

按任意键关闭此窗口. . .