简述归并排序
归并排序
特点：
- 高效
- 稳定
- 时间复杂度最佳/平均/最差： 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
}