归并排序的递归实现与优化

归并排序的递归写法

归并排序的

核心在于如何将数组两个区间重新排序成一个新的数组

，这里需要开辟新的空间，它不可以原地排序。

import java.util.Arrays;

public class MergeSort {

    private MergeSort() {
    }

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

    // 递归函数
    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (l >= r) return;
        int mid = (r - l) / 2 + l;
//        int mid2 = (r + l) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    // 合并区间 arr[l...mid],arr[mid+1...r]
    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r) {
        // 复制一份元素组用于排序，Arrays.copyOfRange()是一个闭区间[] 所以需要复制[l,r+1)
        E[] temp = Arrays.copyOfRange(arr, l, r + 1);
        int i = l, j = mid + 1; // i和j分别指向temp中两端区间的头部
        // 每次都判断arr[i]与arr[j]的大小即temp[i-l]和temp[j-l] l...r区间内
        for (int k = l; k <= r; k++) {
            // i超出中间位置，直接从j中取元素
            if (i > mid) {
                arr[k] = temp[j - l];
                j++;
            } else if (j > r) {
                arr[k] = temp[i - l];
                i++;
            } else if (temp[i - l].compareTo(temp[j - l]) <= 0) {
                arr[k] = temp[i - l];
                i++;
            } else {
                arr[k] = temp[j - l];
                j++;
            }
        }
    }
}
           

进行第一次优化

调用merge函数合并两个区间，合并前arr[l…mid],arr[mid+1…r]是两个有序的区间，此时如果

arr[mid]比arr[mid+1]的时候不需要进行重新排序

，就不需要调用merge函数。所以在递归是加上if语句进行条件约束。

// 如果mid>mid+1的情况下执行merge
if (arr[mid].compareTo(arr[mid + 1]) > 0)
    merge(arr, l, mid, r);
           

最优的情况下，当数组越接近有序，归并排序的速度越快。时间复杂度为O(n)。

使用插入排序优化

如果数组元素个数非常少的话，越大概率是一个近乎有序的数组，使用插入排序进行，插入排序前的常数很小。数组规模小，插入排序速度快于归并排序。

插入排序对小规模的数据，由于常数低，速度反而快。插入排序的优化在高级语言中不一定可行。意义并不大。

public static <E extends Comparable<E>> void isertionSort(E[] arr, int l, int r) {
   for (int i = l; i < r; i++) {
        // 进行暂存
        E temp = arr[i];
        // 实际存储位置
        int j;
        for (j = i; j - 1 >= l && temp.compareTo(arr[j - 1]) < 0; j--)
            arr[j] = arr[j - 1];
        arr[j] = temp;
    }
}

public static <E extends Comparable<E>> void sort(E... arr) {
    sort(arr, 0, arr.length - 1);
}

// 递归函数
private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
    if (r - l <= 15) {
        isertionSort(arr, l, r);
        return;
    }
    int mid = (r - l) / 2 + l;
//        int mid2 = (r + l) / 2;
    sort(arr, l, mid);
    sort(arr, mid + 1, r);
    merge(arr, l, mid, r);
}


// 合并区间 arr[l...mid],arr[mid+1...r]
private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r) {
    // 复制一份元素组用于排序，Arrays.copyOfRange()是一个闭区间[] 所以需要复制[l,r+1)
    E[] temp = Arrays.copyOfRange(arr, l, r + 1);
    int i = l, j = mid + 1; // i和j分别指向temp中两端区间的头部
    // 每次都判断arr[i]与arr[j]的大小即temp[i-l]和temp[j-l] l...r区间内
    for (int k = l; k <= r; k++) {
        // i超出中间位置，直接从j中取元素
        if (i > mid) {
            arr[k] = temp[j - l];
            j++;
        } else if (j > r) {
            arr[k] = temp[i - l];
            i++;
        } else if (temp[i - l].compareTo(temp[j - l]) <= 0) {
            arr[k] = temp[i - l];
            i++;
        } else {
            arr[k] = temp[j - l];
            j++;
        }
    }
}
           

优化merge函数

临时数组开创次数过多，每一次归并都开辟了新的空间。从内存上优化归并排序。在递归调用前开辟一次空间。

public static <E extends Comparable<E>> void sort(E[] arr) {
    E[] temp = Arrays.copyOf(arr, arr.length);
    sort(arr, 0, arr.length - 1, temp);
}

// 递归函数
private static <E extends Comparable<E>> void sort(E[] arr, int l, int r, E[] temp) {
    if (l >= r) return;
    int mid = (r - l) / 2 + l;
//        int mid2 = (r + l) / 2;
    sort(arr, l, mid, temp);
    sort(arr, mid + 1, r, temp);

    // 如果mid>mid+1的情况下执行merge
    if (arr[mid].compareTo(arr[mid + 1]) > 0)
        merge(arr, l, mid, r, temp);

}

// 合并区间 arr[l...mid],arr[mid+1...r]
private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, E[] temp) {
    // 保证temp和arr相应元素相同
    System.arraycopy(arr, l, temp, l, r - l + 1);
    // i和j分别指向temp中两端区间的头部
    int i = l, j = mid + 1;
    // 每次都判断arr[i]与arr[j]的大小即temp[i]和temp[j] l...r区间内
    for (int k = l; k <= r; k++) {
        // i超出中间位置，直接从j中取元素
        if (i > mid) {
            arr[k] = temp[j];
            j++;
        } else if (j > r) {
            arr[k] = temp[i];
            i++;
        } else if (temp[i].compareTo(temp[j]) <= 0) {
            arr[k] = temp[i];
            i++;
        } else {
            arr[k] = temp[j];
            j++;
        }
    }
}