一、归并排序介绍

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer） 策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修 补”在一起，即分而治之）。

二、归并排序思想示意图

1. 基本思想

排序算法-归并排序 - 图1
说明:
可以看到这种结构很像一棵完全二叉树，归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程。

2. 合并相邻有序子序列

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将 [4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤
排序算法-归并排序 - 图2

三、归并排序的应用实例:

一个数组, int[] arr = Array(8, 4, 5, 7, 1, 3, 6, 2 ), 请使用归并排序完成排序。

  1. public class MergetSort {
  3.     public static void main(String[] args) {
  4.         int[] arr = { 8, 4, 5, 7, 1, 3, 6, 2 }; 
  6.         mergeSort(arr, 0, arr.length - 1, temp);
  8.         System.out.println("归并排序后=" + Arrays.toString(arr));
  9.     }
  11.     //分+合方法
  12.     public static void mergeSort(int[] arr, int left, int right, int[] temp) {
  14.         if(left < right) {
  15.             int mid = (left + right) / 2; //中间索引
  16.             //向左递归进行分解
  17.             mergeSort(arr, left, mid, temp);
  18.             //向右递归进行分解
  19.             mergeSort(arr, mid + 1, right, temp);
  20.             //合并
  21.             merge(arr, left, mid, right, temp);
  22.         }
  23.     }
  25.     //合并的方法
  26.     /**
  27.      *
  28.      * @param arr 排序的原始数组
  29.      * @param left 左边有序序列的初始索引
  30.      * @param mid 中间索引
  31.      * @param right 右边索引
  32.      * @param temp 做中转的数组
  33.      */
  34.     public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
  35.         int i = left; // 初始化 i, 左边有序序列的初始索引
  36.         int j = mid + 1; //初始化 j, 右边有序序列的初始索引
  37.         int t = 0; // 指向 temp 数组的当前索引
  39.         //(一)
  40.         //先把左右两边(有序)的数据按照规则填充到 temp 数组
  41.         //直到左右两边的有序序列，有一边处理完毕为止
  42.         while (i <= mid && j <= right) {//继续
  43.             //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
  44.             //即将左边的当前元素，填充到 temp 数组
  45.             //然后 t++, i++
  46.             if(arr[i] <= arr[j]) {
  47.                 temp[t] = arr[i];
  48.                 t += 1;
  49.                 i += 1;
  50.             } else { //反之,将右边有序序列的当前元素，填充到 temp 数组
  51.                 temp[t] = arr[j];
  52.                 t += 1;
  53.                 j += 1;
  54.             }
  55.         }
  57.         //(二)
  58.         //把有剩余数据的一边的数据依次全部填充到 temp
  59.         while( i <= mid) { //左边的有序序列还有剩余的元素，就全部填充到 temp
  60.             temp[t] = arr[i];
  61.             t += 1;
  62.             i += 1;
  63.         }
  64.         while( j <= right) { //右边的有序序列还有剩余的元素，就全部填充到 temp
  65.             temp[t] = arr[j];
  66.             t += 1;
  67.             j += 1;
  68.         }
  70.         //(三)
  71.         //将 temp 数组的元素拷贝到 arr
  72.         //注意，并不是每次都拷贝所有
  73.         t = 0;
  74.         int tempLeft = left; //
  75.         //第一次合并 tempLeft = 0 , right = 1 // tempLeft = 2 right = 3 // tL=0 ri=3
  76.         //最后一次 tempLeft = 0 right = 7
  77.         while(tempLeft <= right) {
  78.             arr[tempLeft] = temp[t];
  79.             t += 1;
  80.             tempLeft += 1;
  81.         }
  82.     }
  83. }