归并排序

算法概述

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列:即先使每个子序列有序，再将子序列合并成较大的有序的子序列。若将两个有序表合并成一个有序表，称为二路归并。（故此,也存在多路归并,路数越多,递归的次数相对越少,处理每次合并时的代码量将会增大）

顾名思义

该算法主要部分有两个：归（递归），并（合并）
1.方向不同，当一个问题的规模很大，怎么办？分而治之（向下调用传入参数规模更小的自己（函数），如果还不能解决，继续调用更小规模的自己，当规模足够小，小到只是两个数的判断，或是看似近乎弱智的问题，一行代码解决它，或是返回一个值给上一层，或是做一个操作，而这个操作也必将影响和决定上一层的结果）
2.小问题解决了，很容易，我的大问题还没解决，怎么办？回溯：（既然大问题的解决完全取决于这些小问题），那么只需合并子问题的解即可，将之一层一层地放大，直至最大规模，就得出了最终结果（并的操作是逐层向上的）
3.合并只是简单地合并吗？并非，假如我得到了两个有序序列，直接一前一后放在一起，这个大序列就有序了？不，是错误的，最终会得到（4,5,1,2,3,6,8,9,1,10,5）这种两个两个有序的结果，因为只是保证了最底层的有序
4.这时就要考虑要从子问题的解中如何获取上层问题的解，由此还可以抽象出 “并” 的算法,将之嵌入到归并算法中，他就能工作了

C++代码实现部分

#include <iostream>
#include <vector>

using namespace std;
vector<int> a;  //向量是表示可以改变大小的数组的序列容器。

//合并的算法
void merge(int start,vector<int> m1, vector<int> m2)
{
	int size1 = m1.size();
	int size2 = m2.size();
	int i=0, j=0;
	while (i<size1||j<size2)
	{
		if (i<size1&&j<size2)
		{
			if (m1[i] < m2[j])
			{
				a[start++] = m1[i++];
			}
			else if (m1[i] > m2[j])
			{
				a[start++] = m2[j++];
			}
			else
			{
				a[start++] = m1[i++];
				a[start++] = m2[j++];
			}
		}
		else if (i<size1)
		{
			while(i<size1)
				a[start++] = m1[i++];
		}
		else
		{
			while (j<size2)
				a[start++] = m2[j++];
		}
	}
}

void Merge_sort(int start,int end)
{
	if (end - start > 1)
	{
		vector<int> m1, m2;
		int end1 = (start + end) / 2;
		int start2 = end1 + 1;
		//划分为两个子问题的解
		Merge_sort(start,end1);
		Merge_sort(start2,end);
		//把两个解拿出来进行合并，得到较大一层的解(即使a中从start到end的序列有序)
		for (int tt = start; tt <= end1; tt++)
			m1.push_back(a[tt]);
		for (int tt = start2; tt <= end; tt++)
			m2.push_back(a[tt]);
		merge(start,m1,m2);
	}
	else
	{
		int tem;
		if (a[start] > a[end])
		{
			tem = a[start];
			a[start] = a[end];
			a[end] = tem;
		}
	}
}

int main()
{
	cout << "请输入一组数字（以-1结束）" << endl;
	int num;
	int i = 0;
	scanf_s("%d",&num);
	while (num != -1)
	{
		a.push_back(num);
		i++;
		scanf_s("%d",&num);
	}
	Merge_sort(0,i-1);   //归并排序
	for (int n = 0; n < i; n++)//打印出结果
	{
		if (n == i-1)
			cout << a[n];
		else
			cout << a[n] << " ";
	}
}

注：既然使用了C++面向对象编程，使用了向量，为什么不用a.sort()方法嘞？

因为用的话就只有一行，而且sort方法是别人写好了的，结合了快速排序-插入排序-堆排序 三种排序算法。

这里我用vector只用了他的不用预先定义大小，动态放入数据的便捷性，突出算法