算法系列（三）归并排序

相信刚进入到编程学习的同学，在基础部分一定会涉及到排序相关的内容，那么归并排序也是最常接触到的。时间多年，像这些算法在工作中对于我本人来说使用比较少，但是最近在复盘的阶段，所以想起这个事情了，在此做一个记录。

这篇文章我们介绍下归并排序，首先来看一张图：

从上面的动图可以看出归并排序的整个流程如下：

1）申请空间。使其大小为两个已经排序序列之和，该空间用于存放合并的列。
2）把长度为n的输入序列分成两个长度为n/2的子序列。
3）将待合并的两个数组，从第一位开始比较，小的放到暂存数组，指针向后移。
4）比较两个指针元素，选择小元素放入合并空间，并移动指针到下个位置。
5）将两个数组剩下的元素追加到暂存数组里，再将暂存数组排序后的元素放到原数组里，两个数组合成一个，这一趟结束

下面来一个java版本的归并排序演示：

package com.demo.Demo;

import java.util.Arrays;

public class BubblingSort {

	private static final int nums[] = { 1, 7, 3, 0, 2, 9, 8, 5, 4, 6 };

	public static void main(String[] args) throws Exception {
		
		int[] rs_nums = sort(nums);
		System.out.println(Arrays.toString(rs_nums));
	}
	
	private static int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length < 2) {
            return arr;
        }
        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(sort(left), sort(right));
    }
	
	private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }

}

运行下看下效果：