简述归并排序

归并排序

特点：

• 高效
• 稳定
• 时间复杂度最佳/平均/最差： O(N log N)

  递归算法有专门的公式来计算时间复杂度

• 空间复杂度 O(N)

  因为开辟了临时的tem_arr数组

一个静态的演示图(from leetcode)

一个动态的演示图

合并实现使用merge函数

inline void merge(vector<int>& arr, int l, int r) {vector<int> tem_arr;int m = (l + r) >> 1;//1 2 3 4  2 4 5 8//0 1 2 3  4 5 6 7//l		m   	 r//i		   jint i = l, j = m+1;while (i <= m && j <= r) {if (arr[i] <= arr[j]) tem_arr.push_back(arr[i++]);else tem_arr.push_back(arr[j++]);}while (i <= m) tem_arr.push_back(arr[i++]);while (j <= r) tem_arr.push_back(arr[j++]);int k = l;for (auto n : tem_arr) {arr[k++] = n;}
}

mergeSort 函数

• 利用merge()方法来进行合并
• 体现了分而治之的算法思想
• 需要掌握递归的思维

inline void mergeSort(vector<int>& arr, int l, int r) {if (l == r) return;       //如果边界重合返回int m = (l + r) >> 1;     //定义一个中点mergeSort(arr, l, m);     //将问题分成左边部分mergeSort(arr, m+1, r);   //将问题分成右边部分merge(arr, l, r);         //调用merge()来进行合并
}

完整代码

#include <iostream>
#include <vector>
#define test_merge
using namespace std;
inline void merge(vector<int>& arr, int l, int r);inline void mergeSort(vector<int>& arr, int l, int r) {if (l == r) return;int m = (l + r) >> 1;mergeSort(arr, l, m);mergeSort(arr, m+1, r);merge(arr, l, r);
}inline void merge(vector<int>& arr, int l, int r) {vector<int> tem_arr;int m = (l + r) >> 1;//1 2 3 4  2 4 5 8//0 1 2 3  4 5 6 7//l		m   	 r//i		   jint i = l, j = m+1;while (i <= m && j <= r) {if (arr[i] <= arr[j]) tem_arr.push_back(arr[i++]);else tem_arr.push_back(arr[j++]);}while (i <= m) tem_arr.push_back(arr[i++]);while (j <= r) tem_arr.push_back(arr[j++]);int k = l;for (auto n : tem_arr) {arr[k++] = n;}
}int main() {ios::sync_with_stdio(false);//加速出入输出流
#ifdef test_merge
// 	测试 merge 函数是否起作用vector<int> arr = {7, 3, 2, 6, 0, 1, 5, 4};mergeSort(arr, 0, arr.size() - 1);for (auto i : arr) {cout << i << ' ';}
#endif
}