公司网站服务器租用,成都龙泉建设网站,wordpress song,飞沐网站建设北京文章目录其他与排序有关的文章原理代码实现复杂度分析其他与排序有关的文章
一学就废的三种简单排序【冒泡、插入、选择】 原理
归并排序#xff08;Merge sort#xff09;#xff1a; 归并排序对元素 递归地 进行 逐层折半分组#xff0c;然后从最小分组开始#xff0c…
文章目录其他与排序有关的文章原理代码实现复杂度分析其他与排序有关的文章
一学就废的三种简单排序【冒泡、插入、选择】 原理
归并排序Merge sort 归并排序对元素 递归地 进行 逐层折半分组然后从最小分组开始逐层进行 比较排序 合并成一个大的分组 。
用一张图表示其原理 图源Krahets 代码实现
void Merge(vectorint nums, int left, int right){// 终止条件if(left right) return;// 递归拆分int mid (leftright)/2;Merge(nums, left, mid);Merge(nums, mid1, right);// 合并排序vectorint tmp(right-left1);// 新建临时数组用以保存排序好的元素int i left, j mid 1, p 0;while(imid jright){ // 升序排列if(nums[i] nums[j]) tmp[p] nums[i];else tmp[p] nums[j];}// 处理剩余左\右子数组元素while(i mid) tmp[p] nums[i];while(j right) tmp[p] nums[j];//结果储存for(int i0; itmp.size(); i){nums[i left] tmp[i];}
}可以进行优化毕竟如果每次递归都新建一个tmp数组是很费时间的
void Merge(vectorint nums, int left, int right, vectorint tmp){// 终止条件if(left right) return;// 递归拆分int mid (leftright)/2;Merge(nums, left, mid, tmp);Merge(nums, mid1, right, tmp);// 合并排序int i left, j mid 1, p left;while(imid jright){ // 升序排列if(nums[i] nums[j]) tmp[p] nums[i];else tmp[p] nums[j];}// 处理剩余左\右子数组元素while(i mid) tmp[p] nums[i];while(j right) tmp[p] nums[j];//结果储存for(int ileft; iright; i){nums[i] tmp[i];}
}复杂度分析
时间复杂度 O(NlogN) 其中 N 为数组长度归并排序使用 O(NlogN) 时间空间复杂度 O(N) 辅助数组 tmp 占用 O(N) 大小的额外空间
