前言：
如今朋友们对“归并排序算法导论”大概比较讲究，姐妹们都需要分析一些“归并排序算法导论”的相关资讯。那么小编也在网络上收集了一些关于“归并排序算法导论””的相关资讯，希望兄弟们能喜欢，大家快快来学习一下吧！文章目录归并排序一、题目描述二、解题思路及代码实现1、解题思路2、C++代码实现三、提交结果总结归并排序一、题目描述
给定一个数组 in，请实现归并排序算法。（来自算法导论分治法一节）
示例:
输入: in = [3,4,2,1,5,0]
输出: ret = [0,1,2,3,4,5]
二、解题思路及代码实现1、解题思路
归并排序的思想–分治法。
分治法思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。
分治法的三个步骤：
1、分解：分解原问题为若干子问题，这些子问题是原问题的规模较小的实例；
2、解决：解决这些子问题，递归地求解各子问题。若子问题的规模足够小，则直接求解；
3、合并：合并这些子问题的解成原问题的解。
归并排序算法完全遵循分治法思想，其操作如下：
1、分解：分解待排序的N个元素的序列成各具N/2个元素的子序列；
2、解决：使用归并排序递归地排序两个子序列；
3、合并：合并两个已排序的子序列以产生已排序的答案；
4、当排序的序列长度为1时，递归开始回升，在这种情况下不需要做任何操作，因为长度为1的每个序列都已排好序。
2、C++代码实现
void merge(vector<int> &array, int left, int middle, int right) { int size_left = middle - left + 1; int size_right = right - middle; int tmp_left[size_left]; int tmp_right[size_right]; for (int i = 0; i < size_left; i++) { tmp_left[i] = array[left + i]; } for (int j = 0; j < size_right; j++) { tmp_right[j] = array[middle + 1 + j]; } int i = 0; int j = 0; for (int k = left; k <= right; k++) { if (i < size_left && j < size_right) { if (tmp_left[i] <= tmp_right[j]) { array[k] = tmp_left[i]; i++; } else { array[k] = tmp_right[j]; j++; } } else { if (i < size_left) { array[k] = tmp_left[i]; i++; } if (j < size_right) { array[k] = tmp_right[j]; j++; } } }}void merge_sort(vector<int> &array, int left, int right) { if (left < right) { //拆分 int middle = (left + right)/2; merge_sort(array, left, middle); merge_sort(array, middle + 1, right); //合并 merge(array, left, middle, right); }}三、提交结果无提交结果。
总结
归并排序是分治法的典型应用，其核心思想是把大问题切割成小规模的同类子问题，递归解决子问题，然后合并子问题的解，最终得到原问题的解。
版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
标签： #归并排序算法导论
