老生常谈比较排序之归并排序(递归)

归并排序里运用到算法里很重要的一个思想——分治法：将原问题分解为几个规模较小但类似于原问题的子问题——《算法导论》。

在每一层递归中都有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 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)