3、数据结构与算法——比较两种排序算法 - liuxiaofei2010S/special-column GitHub Wiki

前两天学习了选择排序和插入排序，现在可以通过代码运行时间来判定两种算法的性能。

代码如下：

public class SortCompare {

public static void main(String[] args) {
    double selectTime = timeRandomInput("SelectSort", 1000, 1000);
    double insertTime = timeRandomInput("InsertSort", 1000, 1000);
    System.out.println("______________________");
    System.out.println("选择排序：" + selectTime);
    System.out.println("插入排序：" + insertTime);
    System.out.println("插入排序比选择排序快：" + (selectTime - insertTime));
    System.out.println("插入排序比选择排序：" + (selectTime / insertTime));
}

private static double time(String arg, int[] a) {
    StopWatch time = new StopWatch();
    if (arg.equals("InsertSort")) {
        InsertSort.sort(a);
    }
    if (arg.equals("SelectSort")) {
        SelectSort.sort(a);
    }
    return time.elapsedTime();
}

/*T个N长度的数组*/
private static double timeRandomInput(String arg, int N, int T) {
    Random random = new Random();
    double total = 0.0;
    for (int i = 0; i < T; i++) {
        int[] a = new int[N];
        for (int k = 0; k < N; k++) {
            a[k] = random.nextInt(100);
        }
        total = total + time(arg, a);
    }
    return total;
}
}

还有一个计算时间的类，代码如下：

public class StopWatch {

private final long start;

private StopWatch() {
    start = System.currentTimeMillis();
}

public double elapsedTime() {
    long end = System.currentTimeMillis();
    return (end - start) / 1000.0;
}
}

通过运行以上代码，可以看出插入排序比选择排序要快，选择排序与插入排序之比约为 1.0 ~1,7之间（只是测试了几次）。今后可以用以上代码测试其他算法性能。