归并排序的Java实现

归并排序的Java实现

归并排序的思想就是将数组拆分成两部分，分别进行排序，然后再归并起来。它运用了分而治之的思想。它的时间复杂度只有 $O(NlogN)$

由此引出两种归并排序方式：

1、自顶向下归并排序，使用递归从上往下拆分可以完成

2、自底向上归并排序，先归并微型数组，再归并得到的数组以此合并成排序好的数组。

无优化版本

以下的版本是没有做任何优化的归并排序方式

import java.util.Arrays;
import java.util.Random;

/**
 * 归并排序
 *
 * @Author Nino 2019/10/3
 */
public class MergeSort<E extends Comparable<E>>{

    /**辅助数组，存储没合并前的数组 */
    private E[] aux;

    /**
     * 合并过程
     *             arr/aux
     * 2   4   5   7 | 3   1   6   8
     * l           m               r
     *
     * @param arr 需要被合并的数组
     * @param l   数组的最左索引
     * @param m   数组的中间分隔索引（m + 1为第二个数组的起始索引）
     * @param r   数组的最右索引
     */
    private void merge(E[] arr, int l, int m, int r) {
        //给辅助数组赋值
        for (int k = l; k <= r; k++) {
            aux[k] = arr[k];
        }
        //左数组的指针
        int i = l;
        //右数组的指针
        int j = m + 1;

        //arr的指针定为k，将左数组和右数组合并到arr[l, r]中
        for (int k = l; k <= r; k++) {
            //左数组指针越界，将右数组剩余元素放进arr
            if (i > m) {
                arr[k] = aux[j++];
            }
            //右数组指针越界，将左数组剩余元素放进arr
            else if (j > r) {
                arr[k] = aux[i++];
            }
            //比较左右数组指针所指位置的大小
            else if (aux[i].compareTo(aux[j]) <= 0) {
                arr[k] = aux[i++];
            } else {
                arr[k] = aux[j++];
            }
        }
    }

    /**
     * 自顶向下归并排序
     * 递归接口
     * @param arr
     */
    public void up2DownSort(E[] arr) {
        //给辅助数组定空间大小（注意这里需要可比较性）
        aux = (E[]) new Comparable[arr.length];
        up2DownSort(arr, 0, arr.length - 1);
    }

    /**
     * 自顶向下归并排序
     * 递归实现
     * @param arr 数组
     * @param l   左边界
     * @param r   右边界
     */
    private void up2DownSort(E[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        
        int mid = l + (r - l) / 2;
        up2DownSort(arr, l, mid);
        up2DownSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    /**
     * 自底向上归并排序
     * 先归并微型数组，再归并得到的微型数组
     *
     * @param arr
     */
    public void down2UpSort(E[] arr) {
        int N = arr.length;
        aux = (E[]) new Comparable[N];
        
        //sz为微型数组大小
        for (int sz = 1; sz < N; sz *= 2) {
            for (int i = 0; i < N - sz; i += sz + sz) {
                // 对 arr[i -> i+sz-1] 和 arr[i+sz -> i+2*sz-1] 进行归并
                merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, N - 1));
            }
        }
    }

    /**
     * 测试用例
     *
     * @param args
     */
    public static void main(String[] args) {
        Random random = new Random();
        Integer[] arr = new Integer[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.valueOf(random.nextInt(20));
        }
        System.out.println(Arrays.asList(arr).toString());
        new MergeSort<Integer>().up2DownSort(arr);
        System.out.println(Arrays.asList(arr).toString());
    }
}

优化版本

优化的方法在于两点：

1、当数组被拆分成很小数组的时候，使用插入排序

2、当两个要合并的数组的边界两个元素满足有序时不进行合并操作

一般情况下，只采用第一种优化方案。

需要写一个插入排序的静态方法，以及更改以下递归函数和自底向上的方法就可以了

	/**
     * 对arr[l...r]的区间使用InsertionSort排序
     * @param arr
     * @param l
     * @param r
     */
    public static void insertionSort(Comparable[] arr, int l, int r){

        for( int i = l + 1 ; i <= r ; i ++ ){
            Comparable e = arr[i];
            int j = i;
            for( ; j > l && arr[j-1].compareTo(e) > 0 ; j--)
                arr[j] = arr[j-1];
            arr[j] = e;
        }
    }

	/**
     * 自顶向下归并排序（优化方案）
     * 递归实现
     * @param arr 数组
     * @param l   左边界
     * @param r   右边界
     */
    private void up2DownSort(E[] arr, int l, int r) {
       	//使用优化方案时，这个部分可以省略
        if (l == r) {
            return;
        }

        //优化方案，对于小规模数组, 使用插入排序
        if( r - l <= 15 ){
            insertionSort(arr, l, r);
            return;
        }

        int mid = l + (r - l) / 2;
        up2DownSort(arr, l, mid);
        up2DownSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

	/**
     * 自底向上归并排序（优化方案）
     * 先归并微型数组，再归并得到的微型数组
     *
     * @param arr
     */
    public void down2UpSort(E[] arr) {
        int N = arr.length;
        aux = (E[]) new Comparable[N];
        
        // Merge Sort Bottom Up 优化
        // 对于小数组, 使用插入排序优化
        for( int i = 0 ; i < N ; i += 16 ){
            InsertionSort.sort(arr, i, Math.min(i+15, N-1) );
        }
        //sz为微型数组大小
        for (int sz = 16; sz < N; sz *= 2) {
            for (int i = 0; i < N - sz; i += sz + sz) {
                // 对 arr[i -> i+sz-1] 和 arr[i+sz -> i+2*sz-1] 进行归并
                merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, N - 1));
            }
        }
    }

如有错误，欢迎指正！