【分治算法】-2.歸并排序

有一篇部落格我覺得動圖非常好：貼上大佬的連結

https://blog.csdn.net/qq_40907279/article/details/81607634

思想：

可以運用分而治之方法來解決排序問題，該問題是将 n 個元素排成非遞減順序。分而治之方法通常用以下的步驟來進行排序算法：若 n 為1，算法終止；否則，将這一進制素集合分割成兩個或更多個子集合，對每一個子集合分别排序，然後将排好序的子集合歸并為一個集合

确實就是後續周遊 即先周遊葉子結點 排序  然後合并到父親節點

#include<iostream>
#include<vector>

using namespace std;

void print(vector<int> a) {
	for (int i = 0; i < a.size(); i++) {
		cout << a[i] << " ";
	}
	cout << endl;
}

//合并算法
void merge(vector<int> &arr, int start, int end, int mid, vector<int> &temp) {
	
	//傳入的兩個有序序列
	int i_start = start;
	int i_end = mid;
	int j_start = mid + 1;
	int j_end = end;


	int length = 0;//用來标記有序數組中的元素

	//合并兩個有序序列
	while (i_start <= i_end&&j_start <= j_end) {
		if (arr[i_start] < arr[j_start]) {
			temp.push_back(arr[i_start]);
			i_start++;
		}
		else {
			temp.push_back(arr[j_start]);
			j_start++;
		}
	}
	//将比較完剩下的元素插入
	while (i_start <= i_end) {
		temp.push_back(arr[i_start]);
		i_start++;
	}
	while (j_start <= j_end) {
		temp.push_back(arr[j_start]);
		j_start++;
	}

	//輔助空間覆寫原空間
	for (int i = 0; i < temp.size(); i++) {
		arr[start + i] = temp[i];
	}
	temp.clear();
}



void merge_sort(vector<int> &arr, int start, int end, vector<int> &temp) {
	
	if (start >= end) return;

	//後序周遊
	int mid = (start + end) / 2;
	merge_sort(arr, start, mid, temp);
	merge_sort(arr, mid + 1, end, temp);
	//兒子節點排序
	merge(arr, start, end, mid, temp);

}

int main() {

	vector<int> arr{ 8,4,5,7,1,3,6,2 };
	vector<int> temp;

	merge_sort(arr, 0, arr.size() - 1, temp);
	print(arr);

	system("pause");

}
           

2.實作申請temp空間 有一點點改動

#include<iostream>
#include<vector>
 
using namespace std;
 
void print(vector<int> a) {
	for (int i = 0; i < a.size(); i++) {
		cout << a[i] << " ";
	}
	cout << endl;
}
 
//合并算法
void merge(vector<int> &arr, int start, int end, int mid,vector<int> temp) {
	
	int i_start = start;
	int i_end = mid;//第一個有序序列
	int j_start = mid + 1;
	int j_end = end;//第二個有序序列
 
	//輔助空間有多少元素
	int length = 0;
 
 
	//合并兩個有序序列
	while(i_start<=i_end && j_start <= j_end){
		
		if (arr[i_start] < arr[j_start]) {
			temp[length] = arr[i_start];
			length++;
			i_start++;
		}
		else {
			temp[length] = arr[j_start];
			length++;
			j_start++;
		}
	}
 
	//其中序列剩的還有值
	while (i_start <= i_end) {
			temp[length] = arr[i_start];
			length++;
			i_start++;
		}
	while (j_start <= j_end) {
		temp[length] = arr[j_start];
		length++;
		j_start++;
	}
	//輔助空間覆寫原空間

	for (int i = 0; i < length; i++)
	{
		arr[start + i] = temp[i];
	}
}
 
 
//拆開排序
void merge_sort(vector<int> &arr, int start, int end, vector<int> temp) {
	//遞歸結束的條件
	if (start >= end) return;
 
	int mid = start +(end-start)/2;
	merge_sort(arr, start, mid, temp);
	merge_sort(arr, mid + 1, end, temp);
	merge(arr, start, end, mid, temp);
}
 
int main() {
 
	vector<int> arr{8,4,5,7,1,3,6,2};

	print(arr);
	//歸并排序
	//輔助空間
 
	vector<int> temp(arr.size(), 0);
	merge_sort(arr, 0, arr.size() - 1,temp);
 
	cout << "排序後：" << endl;
	print(arr);
 
	system("pause");
 
}