排序算法比较

比较方法来自算法四版
java
package xyz.intellij.playground.algs4.sort;

import edu.princeton.cs.algs4.Stopwatch;
import edu.princeton.cs.introcs.StdOut;
import edu.princeton.cs.introcs.StdRandom;

/**
 * 排序算法比较
 */
public class SortCompare {
    /**
     * 使用传入的排序算法排序并返回算法使用的时间
     */
    public static double time(SortTemp alg, Double[] a) {
        Stopwatch stopwatch = new Stopwatch();
        alg.sort(a);
        return stopwatch.elapsedTime();
    }

    /**
     * 使用算法alg将T个长度为N的数组排序
     *
     * @param alg 算法实现
     * @param N   数组长度
     * @param T   数组个数
     * @return 排序所需的时间
     */
    public static double timeRandomInput(SortTemp alg, int N, int T) {
        double total = 0D;
        Double[] array = new Double[N];
        for (int i = 0; i < T; i++) {
            for (int j = 0; j < N; j++) {
                array[j] = StdRandom.uniform();
            }
            total += time(alg, array);
        }
        return total;
    }

    /**
     * 两个算法比较
     *
     * @param alg1
     * @param alg2
     */
    public static void compare(SortTemp alg1, SortTemp alg2) {
        int N = 1000;
        int T = 5000;
        double t1 = timeRandomInput(alg1, N, T);
        double t2 = timeRandomInput(alg2, N, T);
        StdOut.printf("对于 %d 个长度为%d随机Double数组的排序,算法 %s ,", T, N, alg1.getClass().getSimpleName());
        StdOut.printf("比算法 %s 快 %.1f \n", alg2.getClass().getSimpleName(), t2 / t1);
    }

    public static void main(String[] args) {
        compare(new Insertion(), new Selection());
        compare(new Insertion(), new Shell());
        compare(new Insertion(), new Merge());
    }
}
排序算法比较 ​

排序算法比较
