歸并排序的遞歸實作與優化

歸并排序的遞歸寫法

歸并排序的

核心在于如何将數組兩個區間重新排序成一個新的數組

，這裡需要開辟新的空間，它不可以原地排序。

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++;
        }
    }
}