归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
1.自上而下的递归（所有的方法都可以用迭代重写，因此有了第二种方法）
2.自下而上的迭代
归并排序的思想：将两个有序序列合并成一个有序序列
#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) { cout << "merge arr传入的部分" << endl; for (int i = start; i <= end; i++) { cout << arr[i] << " "; } cout << endl; 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++; } //辅助空间覆盖原空间 cout << "局部排序完之后： "; for (int i = 0; i < length; i++) { arr[start + i] = temp[i]; cout << temp[i] << " "; } cout << endl; } //拆开排序 void merge_sort(vector<int> &arr, int start, int end, vector<int> temp) { //递归结束的条件 if (start >= end) return; int mid = start +(end-start)/2; //分组 //左边 cout << "左merge_sort(arr,start:"<<start<<",mid:"<<mid<<",end:" <<end<<")"<< endl; merge_sort(arr, start, mid, temp); //右边 cout << "右merge_sort(arr,mid+1:" << mid+1 << ",end:" << end << ")" << endl; merge_sort(arr, mid + 1, end, temp); //合并 cout << "合并merge(arr,start:" << start << ",mid:" << mid << ",end:" << end << ",)"<< endl; merge(arr, start, end, mid, temp); } int main() { vector<int> arr{8,4,5,7,1,3,6,2}; cout << "原数组:" << endl; print(arr); //归并排序 //辅助空间 vector<int> temp(arr.size(), 0); merge_sort(arr, 0, arr.size() - 1,temp); cout << "排序后：" << endl; print(arr); system("pause"); } #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}; cout << "原数组:" << endl; print(arr); //归并排序 //辅助空间 vector<int> temp(arr.size(), 0); merge_sort(arr, 0, arr.size() - 1,temp); cout << "排序后：" << endl; print(arr); system("pause"); }
代码运行过程分析：
运行结果：
运行树：
时间复杂度分析：来源于大话数据结构截图
