dw怎么做网站相册,做自媒体搬运文章的网站,广州市专业网站建设,应用公园免费版下载前置知识#xff1a;讲解019-算法笔试中处理输入和输出#xff0c;讲解020-递归和master公式
(1)左部分排好序#xff0c;右部分排好序#xff0c;利用merge过程让左右整体有序(2)merge过程:谁小拷贝谁#xff0c;直到左右两部分所有的数字耗尽(3)递归实现和非递归实现(4…前置知识讲解019-算法笔试中处理输入和输出讲解020-递归和master公式
(1)左部分排好序右部分排好序利用merge过程让左右整体有序(2)merge过程:谁小拷贝谁直到左右两部分所有的数字耗尽(3)递归实现和非递归实现(4)时间复杂度O(n*logn)(5)需要辅助数组所以额外空间复杂度O(n)(6)归并排序为什么比O(n^2)的排序快因为比较行为没有浪费!(7)利用归并排序的便利性可以解决很多问题例如归并分治
注意:有些资料说可以用原地归并排序把额外空间复杂度变成O(1)不要浪费时间去学。因为原地归并排序确实可以省空间但是会把复杂度变成O(n^2)
对这个数组arr[6,4,2,3,9,4] ,进行归并排序 挑其中一步来演示 把[2,4,6]和[3,4,9]合并merge 最后再刷回原数组 void merge(vectorint arr,int left, int mid, int right) {int n right - left 1;vectorint help(n,0);int i 0;int a left;int b mid 1;while (a mid b right) {help[i] arr[a] arr[b] ? arr[a] : arr[b];}// 左侧指针右侧指针必有一个越界另一个不越界while (a mid) {help[i] arr[a];}while (b right) {help[i] arr[b];}for (i 0; i n; i) { // 把 help 里面的数据重新刷回到原数组arrarr[ileft] help[i];}
}
1归并排序递归版
// 递归方法
void mergeSort(vectorint arr, int left, int right) {if (left right) return;int mid (left right) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid 1, right);merge(arr, left, mid, right);
}
2归并排序非递归版 // 归并排序非递归版
// 时间复杂度O(n * logn)
// 空间复杂度O(n)
void mergeSort2(vectorint arr) {int n arr.size();// 一共发生O(logn)次for (int left, mid, right, step 1; step n; step 1) {// 内部分组merge时间复杂度O(n)left 0;while (left n) {mid left step - 1;if (mid 1 n) {// 已经没有右侧了break;}// 有右侧,求右侧的右边界right min(left (step 1) - 1, n - 1);// left ... mid mid1 ... right// left ... mid mid1 ... right// left ... mid mid1 ... rightmerge(arr,left, mid, right);left right 1;}}
}
完整代码
#include iostream
#include vector
using namespace std;void merge(vectorint arr,int left, int mid, int right) {int n right - left 1;vectorint help(n,0);int i 0;int a left;int b mid 1;while (a mid b right) {help[i] arr[a] arr[b] ? arr[a] : arr[b];}// 左侧指针右侧指针必有一个越界另一个不越界while (a mid) {help[i] arr[a];}while (b right) {help[i] arr[b];}for (i 0; i n; i) { // 把 help 里面的数据重新刷回到原数组arrarr[ileft] help[i];}
}/*归并排序递归版假设left...right一共 n 个数T(n) 2 * T(n/2) O(n)a 2,b 2,c 1根据master公式时间复杂度O(n * logn)空间复杂度O(n)
*/
// 递归方法
void mergeSort(vectorint arr, int left, int right) {if (left right) return;int mid (left right) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid 1, right);merge(arr, left, mid, right);
}// 归并排序非递归版
// 时间复杂度O(n * logn)
// 空间复杂度O(n)
void mergeSort2(vectorint arr) {int n arr.size();// 一共发生O(logn)次for (int left, mid, right, step 1; step n; step 1) {// 内部分组merge时间复杂度O(n)left 0;while (left n) {mid left step - 1;if (mid 1 n) {// 已经没有右侧了break;}// 有右侧,求右侧的右边界right min(left (step 1) - 1, n - 1);// left ... mid mid1 ... right// left ... mid mid1 ... right// left ... mid mid1 ... rightmerge(arr,left, mid, right);left right 1;}}
}int main() {vectorint arr { 6,4,2,3,9,4};int n arr.size();mergeSort(arr, 0, n - 1);//mergeSort2(arr);for (int i 0; i n; i) {cout arr[i] endl;}system(pause);return 0;
}
完整图 参考和推荐视频
算法讲解021【必备】归并排序_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1wu411p7r7/?spm_id_from333.999.list.card_archive.clickvd_sourcea934d7fc6f47698a29dac90a922ba5a3
