算法之排序-选择排序与插入排序的比较

文章目录
  1. 1. 性质D
  2. 2. 比较两种算法

我们将通过以下步骤比较两个算法：

  • 实现并调试他们
  • 分析他们的基本性质
  • 对他们的相对性做出猜想
  • 用实验证明我们的猜想

前面两节的算法已经实现了第一步，命题A，命题B，命题C组成了第二步，下面的性质D是第三步，之后的比较两种排序算法的SortCompare类将会完成第四步。

性质D

对于随机排序的无重复主键的数组，插入排序和选择排序的运行时间是平方级别的，两者之比应该是一个较小的常数。

比较两种算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public class SortCompare {
    /**
     * 对排序算法进行计时
     * @param alg 排序算法
     * @param a 数组
     * @return
     */
    public static double time(String alg, Double[] a) {
        Profiler.begin();

        if (alg.equals("Insertion")) {
            Insertion.sort(a);
        }
        if (alg.equals("Selection")) {
            Selection.sort(a);
        }

        return Profiler.end();
    }

    /**
     * 使用算法alg将T个长度为N的数组排序
     * @param alg 算法
     * @param N 数组长度
     * @param T T个数组
     * @return
     */
    public static double timeRandomInput(String alg,int N, int T){
        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] = 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);//算法1的总时间
        double t2 = timeRandomInput(alg2,N,T);//算法2的总时间

        System.out.printf("For %d random Doubles\n %s is ",N,alg1);
        System.out.printf("%.1f times faster than %s\n ",t2/t1,alg2);

    }

    /**
     * Returns a random real number uniformly in [0, 1).
     *
     * @return a random real number uniformly in [0, 1)
     */
    public static double uniform() {
        return new Random().nextDouble();
    }
//程序参数为 Insertion Selection 1000 100 ,运行结果：
//    For 1000 random Doubles
//    Insertion is 1.8 times faster than Selection
}