如何在Java与Python实现一个归并排序算法

如何在Java与python实现一个归并排序算法？针对这个问题，这篇文章详细介绍了相对应的分析和解答，希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

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

在每一层递归中都有3个步骤：

分解问题

解决问题

合并问题的解

举例待排序数组：{6, 5, 3, 1, 7, 2, 4}，将它原始序列做分解。

可以经过不断的递归分解可以看到已经把原始数组序列不断分解为最小单位，接下来不妨将它们看做是二叉树的叶子节点。

将他们进行两两归并排序形成二叉树（也称为2路归并算法），可见二叉树的根节点即为最终序列。在这个过程中我们完成了剩余的两个步骤：解决问题和合并问题。

理论很简单，实践很“复杂”。对于归并排序的理论从上面的二叉树就看的很明白，将原始待排序数组不断分解最后看成是二叉树的叶子节点，再把它们两两排形成新的节点，逐渐归并为一个节点，此时的节点即为排好序的数组序列。

Java

package com.alGorithm.sort.merge;import java.util.Arrays;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));  }    private static int[] mergeSort(int[] nums) {    segment(nums, 0, nums.length - 1);    return nums;  }    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);  }    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++];    }  }}