信誉好的网站开发,福州市工程造价信息网,做外贸网站需要什么,wordpress 获取头像归并排序
特点#xff1a;
高效稳定时间复杂度最佳/平均/最差#xff1a; O(N log N) 递归算法有专门的公式来计算时间复杂度 空间复杂度 O(N) 因为开辟了临时的tem_arr数组 一个静态的演示图(from leetcode) 一个动态的演示图 合并实现使用merge函数
inline void merge(v…归并排序
特点
高效稳定时间复杂度最佳/平均/最差 O(N log N) 递归算法有专门的公式来计算时间复杂度 空间复杂度 O(N) 因为开辟了临时的tem_arr数组
一个静态的演示图(from leetcode) 一个动态的演示图 合并实现使用merge函数
inline void merge(vectorint arr, int l, int r) {vectorint 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 m1;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(vectorint arr, int l, int r) {if (l r) return; //如果边界重合返回int m (l r) 1; //定义一个中点mergeSort(arr, l, m); //将问题分成左边部分mergeSort(arr, m1, r); //将问题分成右边部分merge(arr, l, r); //调用merge()来进行合并
}完整代码
#include iostream
#include vector
#define test_merge
using namespace std;
inline void merge(vectorint arr, int l, int r);inline void mergeSort(vectorint arr, int l, int r) {if (l r) return;int m (l r) 1;mergeSort(arr, l, m);mergeSort(arr, m1, r);merge(arr, l, r);
}inline void merge(vectorint arr, int l, int r) {vectorint 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 m1;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 函数是否起作用vectorint arr {7, 3, 2, 6, 0, 1, 5, 4};mergeSort(arr, 0, arr.size() - 1);for (auto i : arr) {cout i ;}
#endif
}
