归并排序及优化(Java实现)

目录：归并排序

|-普通归并排序

|-归并排序优化：利用插入排序

|-归并排序继续优化：归并前判断

普通归并排序

public class MergeSort {
    /**
     * @param arr   待排序的数组
     * @param left  本次归并的左边界
     * @param mid   本次归并的中间位置，也就是分界线
     * @param right 本次归并的右边界
     * @param <T>   泛型
     * @local aux   辅助空间(Auxiliary Space)
     */
    private static <T extends Comparable<? super T>> void merge(T[] arr, int left, int mid, int right) {
        T[] aux = java.util.Arrays.copyOfRange(arr, left, right + 1);

        //aux，i j分别是这两半的起始指针。将这两个闭区间归并[left ... mid]   [mid + 1 ... right]
        int i = left;
        int j = mid + 1;

        for (int t = left; t <= right; t++) {//把arr数组中的[left...right]区间都覆盖了，就完事了
            if (i > mid) { //i == mid + 1 时越界(跃出左半数组)
                arr[t] = aux[j++ - left];
            } else if (j > right) {//j == right + 1 时越界(跃出右半数组)
                arr[t] = aux[i++ - left];
            } else if (aux[i - left].compareTo(aux[j - left]) < 0) {//如果i-left小，那么插入。(左半边数组的指针所指的数小)
                arr[t] = aux[i++ - left];
            } else { //如果j-left小，那么插入。(右半边数组的指针所指的数小)
                arr[t] = aux[j++ - left];
            }
        }
    }

    private static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        int mid = (left + right) / 2;
        sort(arr, left, mid);
        sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    public static <T extends Comparable<? super T>> void sort(T[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static void printArr(Object[] arr) {
        for (Object o : arr) {
            System.out.print(o);
            System.out.print("\t");
        }
        System.out.println();
    }

    public static void main(String args[]) {
        Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
        printArr(arr);//3   5   1   7   2   9   8   0   4   6
        sort(arr);
        printArr(arr);//0   1   2   3   4   5   6   7   8   9
    }
}