[数据结构与算法]【排序算法】C++归并排序原理及代码实现

归并排序是用分治思想所提出的一种排序方法，它的思想就是把一组数据先拆再合，合的时候从单个开始合的时候就进行排序。

如图所示，在合的时候相邻两个两两组合并排序。
算法步骤：
1、从单个元素开始申请一个两个子元素合并后大小的空间。
2、因为已知两个子数组是排序完全的，所以只要从左到右以次比较，谁小放前面即可。
3、排序完成后，开始迭代，直到整组数据排序完成。

#include<iostream>
#include<new>

void merge(int* a, int start, int end);
void mergesort(int* a, int start1, int end1, int start2, int end2);

int main()
{
	using namespace std;
	int* a;	//排序数组
	int n;	//数组大小
	cin >> n;
	a = new int[n];
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	merge(a, 0,n-1);
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << endl;
	}
	return 0;
}

void merge(int* a, int start,int end)		//分
{
	if (start == end)	;
	else
	{
		merge(a, start, int((start + end) / 2));
		merge(a, int((start + end) / 2)+1, end);
		mergesort(a, start, int((start + end) / 2), int((start + end) / 2)+1, end);

	}
}

void mergesort(int* a, int start1, int end1,int start2, int end2)
{
	int* temp = new int[end2 - start1 + 1];
	int p=start1;
	int q=start2;
	int o = 0;
	while (p <= end1 && q <= end2)
	{
		if (a[p] < a[q])
		{
			temp[o] = a[p];
			o++;
			p++;
		}
		else if(a[p] > a[q])
		{
			temp[o] = a[q];
			o++;
			q++;
		}
	}
	while (p <= end1)
	{
		temp[o] = a[p];
		o++;
		p++;
	}
	while (q <= end2)
	{
		temp[o] = a[q];
		o++;
		q++;
	}
	for (int i = start1; i <= end2; i++)
	{
		a[i] = temp[i - start1];
	}
	delete temp; 
}