[Day26]程序菜鸟自学C++资料结构演算法 – 合并排序法(Merge Sort)

前言：今天要来介绍第二种分割资料的排序法，就让我们来看看这个有趣的排序法吧！

合并排序：

首先会将一笔资料分割成两部分，然後再将这两部分对半切，直到切到资料的最小单位，之後从小单位开始整合排序，在逐渐合并成排序好的资料。可以重新安排一线性串列成为指定顺序的资料，是一种外部储存装置最常使用的排序方法，因为储存在硬碟或循序档案上的资料就是一种线性串列。

执行效率分析：合并排序的执行效率分成两部分，在合并部分和排序键直数成正比，时间复杂度为O(n)；分割部分每次会分二分之一，处理次数大概为Log n次完成排序，综合两次执行其时间复杂度为O(n Log n)。

合并排序需要使用递回函式，所以要有额外的记忆体空间来处理递回方法。是一种具有稳定性的排序法，因为只有在合并时会交换元素，所以不会交换到相同键值的元素。

合并排序实作：在写好排序法之前，先来实现如何将两组以排序好的数列合并且整理好，这是合并排序的第一步。

将0~7(共8个元素)的序列，和後面3个元素合并成大小为10的序列。

完成此步骤後就可以来撰写合并排序了。

这样就排序成功了喔！

本日小结：这样就介绍完了两个高等的分割资料排序，合并排序法只要分割至最小部分，然後俩俩经过排序再合并成一个数列就完成了，合并时的程序比较复杂也很容易在那边出错，设计的程序的时候要格外小心。铁人赛也已经接近尾声，之後的篇幅也会着重介绍其他的排序法和实作给大家看，剩下最後几天大家一起加油吧୧| ⁰ ᴥ ⁰ |୨

template <typename T>
void merge(const vector<T>& data, vector<T>& out, const int s, const int M, const int N) {
	//s&M指向两个子集合相应的位置
	//data是输入的数列，out是输出的数列
	int i = s, j = M + 1, k = s;
	while (i <= M && j <= N) { //两个序列都还有数据
		if (data[i] < data[j]) 
			out[k++] = data[i++];
		else
			out[k++] = data[j++];
	} //序列剩余数据依次写入目标序列
	while (i <= M) 
		out[k++] = data[i++];
	while (j <= N) 
		out[k++] = data[j++];
}

template <typename T>
void copy(const vector<T>& B, vector<T>& A, int s, int e) {
	//拷贝B到A内；s,t为范围
	for (int i = s; i <= e; i++)
		A[i] = B[i];
}

template <typename T>
void merge_sort(vector<T>& A, int s, int t) {
	if (s == t) { return; } //代表已经排序好，可以直接传回
	merge_sort(A, s, (s + t) / 2); //解决此区间(s,(s + t) / 2)的递回问题
	merge_sort(A, (s + t) / 2 + 1, t); //解决另一区间的问题
	vector<T> B(A.size()); //定义数列B
	merge(A, B, s, (s + t) / 2, t); //将A内的元素和B( s, (s + t) / 2, t)区间合并
	copy(B, A, s, t); //拷贝B至A内可以保证排序好的数列不会再被动到
}