首页 > 代码库 > 4.比较排序之归并排序（递归）
4.比较排序之归并排序（递归）
归并排序里运用到算法里很重要的一个思想——分治法：将原问题分解为几个规模较小但类似于原问题的子问题——《算法导论》。在每一层递归中都有3个步骤：
1.分解问题
2.解决问题
3.合并问题的解
举例待排序数组：{6, 5, 3, 1, 7, 2, 4}，将它原始序列做分解。
可以经过不断的递归分解可以看到已经把原始数组序列不断分解为最小单位，接下来不妨将它们看做是二叉树的叶子节点。
将他们进行两两归并排序形成二叉树（也称为2路归并算法），可见二叉树的根节点即为最终序列。在这个过程中我们完成了剩余的两个步骤：解决问题和合并问题。
理论很简单，实践很“复杂”。对于归并排序的理论从上面的二叉树就看的很明白，将原始待排序数组不断分解最后看成是二叉树的叶子节点，再把它们两两排形成新的节点，逐渐归并为一个节点，此时的节点即为排好序的数组序列。
Java
1 package com.algorithm.sort.merge; 2 3 import java.util.Arrays; 4 5 /** 6 * 归并排序（递归） 7 * Created by yulinfeng on 2017/6/23. 8 */ 9 public class Merge {10 public static void main(String[] args) {11 int[] nums = {6, 5, 3, 1, 7, 2, 4};12 nums = mergeSort(nums);13 System.out.println(Arrays.toString(nums));14 }15 16 /**17 * 归并排序18 * @param nums 待排序数组序列19 * @return 排好序的数组序列20 */21 private static int[] mergeSort(int[] nums) {22 segment(nums, 0, nums.length - 1);23 return nums;24 }25 26 /**27 * 递归切分待排28 * @param nums 待切分数组29 * @param left 待切分最后第一个元素的索引30 * @param right 待切分数组最后一个元素的索引31 */32 private static void segment(int[] nums, int left, int right) {33 if (left >= right)34 return;35 // 找出中间索引36 int center = (left + right) / 2;37 // 对左边数组进行递归38 segment(nums, left, center);39 // 对右边数组进行递归40 segment(nums, center + 1, right);41 // 合并42 merge(nums, left, center, right);43 }44 45 /**46 * 两两归并排好序的数组（2路归并）47 * @param nums 带排序数组对象48 * @param left 左边数组的第一个索引49 * @param center 左数组的最后一个索引，center + 1右数组的第一个索引50 * @param right 右数组的最后一个索引51 */52 private static void merge(int[] nums, int left, int center, int right) {53 int[] tmpArray = new int[nums.length];54 int rightIndex = center + 1; // 右数组第一个元素索引55 int tmpIndex = left; //临时数组索引56 int begin = left; // 缓存左数组第一个元素的索引，用于将排好序的数组拷贝回原数组57 while (left <= center && rightIndex <= right) {58 if (nums[left] <= nums[rightIndex]) {59 tmpArray[tmpIndex++] = nums[left++];60 } else {61 tmpArray[tmpIndex++] = nums[rightIndex++];62 }63 }64 while (left <= center) {65 tmpArray[tmpIndex++] = nums[left++];66 }67 while (rightIndex <= right) {68 tmpArray[tmpIndex++] = nums[rightIndex++];69 }70 while (begin <= right) {71 nums[begin] = tmpArray[begin++];72 }73 }74 }
Python3
1 #二路归并排序（递归） 2 def merge_sort(nums): 3 segment(nums, 0, len(nums) - 1) 4 return nums 5 6 #切分待排序数组 7 def segment(nums, left, right): 8 if left >= right: 9 return10 center = int((left + right) / 2)11 segment(nums, left, center)12 segment(nums, center + 1, right)13 merge(nums, left, center, right)14 15 #两两归并排好序的数组（二路归并）16 def merge(nums, left, center, right):17 tmpArray = [0] * len(nums)18 rightIndex = center + 1 #右数组的第一个元素索引19 tmpIndex = left20 begin = left21 while left <= center and rightIndex <= right:22 if nums[left] <= nums[rightIndex]:23 tmpArray[tmpIndex] = nums[left]24 tmpIndex += 125 left += 126 else:27 tmpArray[tmpIndex] = nums[rightIndex]28 tmpIndex += 129 rightIndex += 130 while left <= center:31 tmpArray[tmpIndex] = nums[left]32 tmpIndex += 133 left += 134 while rightIndex <= right:35 tmpArray[tmpIndex] = nums[rightIndex]36 tmpIndex += 137 rightIndex += 138 while begin <= right:39 nums[begin] = tmpArray[begin]40 begin += 141 42 nums = [6, 5, 3, 1, 7, 2, 4]43 nums = merge_sort(nums)44 print(nums)
4.比较排序之归并排序（递归）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。