Java归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

算法步骤：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置

3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

4. 重复步骤3直到某一指针达到序列尾

5. 将另一序列剩下的所有元素直接复制到合并序列尾.

步骤2~5为合并两个有序区间

算法图示

算法性能

排序算法	平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	稳定性
归并排序	O(N*logN)	O(N*logN)	O(N*logN)	O(n)	稳定

Java代码

package com.sort;

import java.util.Random;

public class Main5 {

    /**
     * 从下到大归并排序
     * 
     * @param array  待排序的数组
     * @param begin 开始位置
     * @param end  结束位置
     * @param backups 辅助空间，不是必须这样写的，也可以直接在合并的时候创建一个
     */
    private static void sort(int[] array, int begin, int end, int[] backups) {
        if (begin < end) {
            // 均分为左右部分
            int mid = (begin + end) / 2;
            // 递归调用左边排序
            sort(array, begin, mid, backups);
            // 递归调用右边排序
            sort(array, mid + 1, end, backups);
            // 将两个有序数组合并
            int left = begin;
            int right = mid + 1;
            int k = begin;
            // 比较左右两边第一个元素，较小的放入辅助空间，然后后移一位，一直到左右两边有一个全部放入
            while (left <= mid && right <= end) {
                if (array[left] > array[right]) {
                    backups[k++] = array[right++];
                } else {
                    backups[k++] = array[left++];
                }
            }

            // 如果左边没有放完，那么将左边全部拷贝到辅助空间里面
            while (left <= mid) {
                backups[k++] = array[left++];
            }
            // 如果右边没有放完，那么将右边全部拷贝到辅助空间里面
            while (right <= end) {
                backups[k++] = array[right++];
            }

            // 将辅助控件里面的数据放回原来的数组
            left = begin;
            while (left <= end) {
                array[left] = backups[left++];
            }
        }
    }

    /**
     * 获取指定长度的随机数组
     */
    public static int[] getRandomArray(int n) {
        int[] array = new int[n];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(500);
        }
        return array;
    }

    /**
     * 打印指定数组
     */
    public static void outputArray(int[] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        int[] array = getRandomArray(5);
        //一次创建好辅助空间，免得合并的时候再创建，这一步不是必须的
        int[] backups = new int[array.length];
        outputArray(array);
        sort(array, 0, array.length - 1, backups);
        outputArray(array);
    }
}