合併排序與插入排序

Question

我在Algorithms in Java 4th edition中實施合併排序。 我的基本合併排序工作，並且我想通過在數組大小小於7時使用插入排序來改進算法。 我認爲這顯然是一種有效的改進，但實際上原始的改進比原來的更快數據。

這是我的改進的合併排序，截留值= 7：

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) { 

    // Copy to aux[] 
    for (int i = lo; i <= hi; i++) { 
    aux[i] = a[i]; 
    } 

    // Merge back to a[] 
    int i = lo, j = mid + 1; 
    for (int k = lo; k <= hi; k++) { 
    if  (i > mid)    a[k] = aux[j++]; 
    else if (j > hi)    a[k] = aux[i++]; 
    else if (less(aux[i], aux[j])) a[k] = aux[i++]; 
    else       a[k] = aux[j++]; 
    } 
} 

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) { 

    // #1 improvement 
    // Stop condition for this recursion. 
    // This time we add a CUTOFF, when the items in array 
    // is less than 7, we will use insertion sort. 
    if (hi <= lo + CUTOFF - 1) { 
    Insertion.sort(a, lo, hi); 
    return; 
    } 

    int mid = lo + (hi - lo)/2; 
    sort(a, aux, lo, mid); 
    sort(a, aux, mid + 1, hi); 
    if (!less(a[mid+1], a[mid])) return; 
    merge(a, aux, lo, mid, hi); 
} 

public static void sort(Comparable[] a) { 
    Comparable[] aux = new Comparable[a.length]; 
    sort(a, aux, 0, a.length - 1); 
} 

插入排序代碼：

public static void sort(Comparable[] a, int lo, int hi) { 
    for (int i = lo; i <= hi; i++) { 
    for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) { 
     exch(a, j, j - 1); 
    } 
    } 
} 

我用SortCompare.java比較執行時間：

public class SortCompare { 

    public static double time(String alg, Comparable[] a) { 
    Stopwatch timer = new Stopwatch(); 
    if (alg.equals("Insertion")) Insertion.sort(a); 
    if (alg.equals("Selection")) Selection.sort(a); 
    if (alg.equals("Shell")) Shell.sort(a); 
    if (alg.equals("Merge")) Merge.sort(a); 
    if (alg.equals("MergeWithImprovements")) MergeWithImprovements.sort(a); 
    //if (alg.equals("Quick")) Quick.sort(a); 
    //if (alg.equals("Heap")) Heap.sort(a); 
    if (alg.equals("InsertionWithSentinel")) InsertionWithSentinel.sort(a); 
    return timer.elapsedTime(); 
    } 

    public static double timeRandomInput(String alg, int N, int T) { 
    // Use alg to sort T random arrays of length N. 
    double total = 0.0; 
    Double[] a = new Double[N]; 
    for (int t = 0; t < T; t++) { 
     for (int i = 0; i < N; i++) { 
     a[i] = StdRandom.uniform(); 
     } 
     total += time(alg, a); 
    } 
    return total; 
    } 

    public static void main(String[] args) { 
    String alg1 = args[0]; 
    String alg2 = args[1]; 
    int N = Integer.parseInt(args[2]); 
    int T = Integer.parseInt(args[3]); 
    double t1 = timeRandomInput(alg1, N, T); // Total for alg1 
    double t2 = timeRandomInput(alg2, N, T); 
    StdOut.printf("For %d random Doubles\n %s is", N, alg1); 
    StdOut.printf(" %.1f times faster than %s\n", t2/t1, alg2); 
    } 
} 

我生成了100個數組，每個數組有10000個元素。最初的合併排序比改進的快30倍！

Answer 1

你插入排序函數肯定是錯誤的。請注意0​​結束條件。你通過[lo..hi]，但你的代碼可以迭代j一直到1。我想你想要的東西是這樣的：

public static void sort(Comparable[] a, int lo, int hi) { 
    for (int i = lo + 1; i <= hi; i++) { 
    for (int j = i; j > lo && less(a[j], a[j - 1]); j--) { 
     exch(a, j, j - 1); 
    } 
    } 
}