7、归并排序

1、归并排序

归并排序：O(N * logN)

public class MergeSort {

    private MergeSort() {
    }

    /**
     * 归并排序
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    /**
     * 归并排序 arr[l, r]
     */
    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (l >= r) return;

        int mid = l + (r - l) / 2;
        sort(arr, l, mid);     // arr[l, mid]
        sort(arr, mid + 1, r); // arr[mid + 1, r]

        merge(arr, l, mid, r);
    }

    /**
     * 合并两个有序数组 arr[l, mid] 和 arr[mid + 1, r], 使得 arr[l, r] 整体有序
     */
    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r) {
        E[] temp = Arrays.copyOfRange(arr, l, r + 1);

        int p1 = 0;           // temp[0, mid - l]
        int p2 = mid + 1 - l; // temp[mid + 1 - l, r - l]
        int i = l;            // arr[l, r]

        while (p1 <= mid - l && p2 <= r - l) arr[i++] = temp[p1].compareTo(temp[p2]) <= 0 ? temp[p1++] : temp[p2++];
        while (p1 <= mid - l) arr[i++] = temp[p1++];
        while (p2 <= r - l) arr[i++] = temp[p2++];
    }
}

2、归并排序优化

归并排序：O(N * logN)
优化 1：merge 条件, 对完全有序的数组 O(n)
优化 2：数据量小的时候(<=16)采用插入排序
优化 3：避免频繁的在内存中开辟空间

public class MergeSortPlus {
    
    private MergeSortPlus() {
    }

    /**
     * 归并排序
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        E[] temp = (E[]) new Comparable[arr.length]; // 优化 3: 避免频繁的在内存中开辟空间
        sort(arr, 0, arr.length - 1, temp);
    }

    /**
     * 归并排序 arr[l, r]
     */
    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r, E[] temp) {
        if (r - l <= 15) {
            InsertionSort.sort(arr, l, r); // 优化 2: 数据量小的时候(<=16)采用插入排序
            return;
        }
        
        int mid = l + (r - l) / 2;
        sort(arr, l, mid, temp);     // arr[l, mid]
        sort(arr, mid + 1, r, temp); // arr[mid + 1, r]
        
        if (arr[mid].compareTo(arr[mid + 1]) > 0) merge(arr, l, mid, r, temp); // 优化 1: merge 条件
    }

    /**
     * 合并两个有序数组 arr[l, mid] 和 arr[mid + 1, r], 使得 arr[l, r] 整体有序
     */
    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, E[] temp) {
        System.arraycopy(arr, l, temp, l, r - l + 1);
        
        int p1 = l;       // temp[l, mid]
        int p2 = mid + 1; // temp[mid + 1, r]
        int i = l;        // arr[l, r]
        
        while (p1 <= mid && p2 <= r) arr[i++] = temp[p1].compareTo(temp[p2]) <= 0 ? temp[p1++] : temp[p2++];
        while (p1 <= mid) arr[i++] = temp[p1++];
        while (p2 <= r) arr[i++] = temp[p2++];
    }
}

3、自底向上归并排序

我们上面实现的归并排序，采用递归的写法，自顶向下进行归并排序
在这里我们换个方式，采用非递归的写法，自底向上实现归并排序

public class MergeSortBU {
    
    private MergeSortBU() {
    }

    /**
     * 自底向上归并排序
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        int n = arr.length;
        E[] temp = (E[]) new Comparable[n];
        
        // 对 arr[0, n - 1] 中所有的 arr[i, i + 15], 使用插入排序法
        for (int i = 0; i < n; i += 16) {
            InsertionSort.sort(arr, i, Math.min(i + 15, n - 1));
        }
        
        // 遍历合并的区间长度(把 2 个区间合并成 1 个区间)
        for (int size = 16; size < n; size += size) {
            // 合并 arr[i, i + size - 1] 和 arr[i + size, i + size + size - 1]
            for (int i = 0; i + size < n; i += 2 * size) {
                if (arr[i + size - 1].compareTo(arr[i + size]) > 0) {
                    merge(arr, i, i + size - 1, Math.min(i + size + size - 1, n - 1), temp);
                }
            }
        }
    }

    /**
     * 合并两个有序数组 arr[l, mid] 和 arr[mid + 1, r], 使得 arr[l, r] 整体有序
     */
    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, E[] temp) {
        System.arraycopy(arr, l, temp, l, r - l + 1);
        
        int p1 = l;       // temp[l, mid]
        int p2 = mid + 1; // temp[mid + 1, r]
        int i = l;        // arr[l, r]
        
        while (p1 <= mid && p2 <= r) arr[i++] = temp[p1].compareTo(temp[p2]) <= 0 ? temp[p1++] : temp[p2++];
        while (p1 <= mid) arr[i++] = temp[p1++];
        while (p2 <= r) arr[i++] = temp[p2++];
    }
}