2
我在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倍!
有趣的是,如果你不會問任何問題,那麼去工作吧,因爲你還沒有問任何問題。 – Azad
是不是這個算法存在於java中? – AKS