下面小编就为大家带来一篇老生常谈比较排序之归并排序(递归)。小编觉得挺不错的，现在就分享给大家，也给大家做个参考。一起跟随小编过来看看吧
归并排序里运用到算法里很重要的一个思想――分治法：将原问题分解为几个规模较小但类似于原问题的子问题――《算法导论》。
在每一层递归中都有3个步骤：
1.分解问题
2.解决问题
3.合并问题的解
举例待排序数组：{6, 5, 3, 1, 7, 2, 4}，将它原始序列做分解。
可以经过不断的递归分解可以看到已经把原始数组序列不断分解为最小单位，接下来不妨将它们看做是二叉树的叶子节点。
将他们进行两两归并排序形成二叉树（也称为2路归并算法），可见二叉树的根节点即为最终序列。在这个过程中我们完成了剩余的两个步骤：解决问题和合并问题。
理论很简单，实践很“复杂”。对于归并排序的理论从上面的二叉树就看的很明白，将原始待排序数组不断分解最后看成是二叉树的叶子节点，再把它们两两排形成新的节点，逐渐归并为一个节点，此时的节点即为排好序的数组序列。
Java
package com.algorithm.sort.merge; import java.util.Arrays; /** * 归并排序（递归） * Created by yulinfeng on 2017/6/23. */ public class Merge { public static void main(String[] args) { int[] nums = {6, 5, 3, 1, 7, 2, 4}; nums = mergeSort(nums); System.out.println(Arrays.toString(nums)); } /** * 归并排序 * @param nums 待排序数组序列 * @return 排好序的数组序列 */ private static <span style="color:transparent">来源gaodai#ma#com搞*代#码网</span>int[] mergeSort(int[] nums) { segment(nums, 0, nums.length - 1); return nums; } /** * 递归切分待排 * @param nums 待切分数组 * @param left 待切分最后第一个元素的索引 * @param right 待切分数组最后一个元素的索引 */ private static void segment(int[] nums, int left, int right) { if (left >= right) return; // 找出中间索引 int center = (left + right) / 2; // 对左边数组进行递归 segment(nums, left, center); // 对右边数组进行递归 segment(nums, center + 1, right); // 合并 merge(nums, left, center, right); } /** * 两两归并排好序的数组（2路归并） * @param nums 带排序数组对象 * @param left 左边数组的第一个索引 * @param center 左数组的最后一个索引，center + 1右数组的第一个索引 * @param right 右数组的最后一个索引 */ private static void merge(int[] nums, int left, int center, int right) { int[] tmpArray = new int[nums.length]; int rightIndex = center + 1; // 右数组第一个元素索引 int tmpIndex = left; //临时数组索引 int begin = left; // 缓存左数组第一个元素的索引，用于将排好序的数组拷贝回原数组 while (left <= center && rightIndex <= right) { if (nums[left] <= nums[rightIndex]) { tmpArray[tmpIndex++] = nums[left++]; } else { tmpArray[tmpIndex++] = nums[rightIndex++]; } } while (left <= center) { tmpArray[tmpIndex++] = nums[left++]; } while (rightIndex <= right) { tmpArray[tmpIndex++] = nums[rightIndex++]; } while (begin <= right) { nums[begin] = tmpArray[begin++]; } } }
Python3
#二路归并排序（递归） def merge_sort(nums): segment(nums, 0, len(nums) - 1) return nums #切分待排序数组 def segment(nums, left, right): if left >= right: return center = int((left + right) / 2) segment(nums, left, center) segment(nums, center + 1, right) merge(nums, left, center, right) #两两归并排好序的数组（二路归并） def merge(nums, left, center, right): tmpArray = [0] * len(nums) rightIndex = center + 1 #右数组的第一个元素索引 tmpIndex = left begin = left while left <= center and rightIndex <= right: if nums[left] <= nums[rightIndex]: tmpArray[tmpIndex] = nums[left] tmpIndex += 1 left += 1 else: tmpArray[tmpIndex] = nums[rightIndex] tmpIndex += 1 rightIndex += 1 while left <= center: tmpArray[tmpIndex] = nums[left] tmpIndex += 1 left += 1 while rightIndex <= right: tmpArray[tmpIndex] = nums[rightIndex] tmpIndex += 1 rightIndex += 1 while begin <= right: nums[begin] = tmpArray[begin] begin += 1 nums = [6, 5, 3, 1, 7, 2, 4] nums = merge_sort(nums) print(nums)
以上就是老生常谈比较排序之归并排序(递归)的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：老生常谈比较排序之归并排序(递归)
转载请注明原文链接：老生常谈比较排序之归并排序(递归)
