【算法】排序（插曲）快慢排序效率

正文之前

写了好几篇排序算法的文章，刚好碰上课程作业，需要比较一种慢排序和一种快排序的效率，所以《排序》系列文章中间就安排了这个小插曲，本文选取的排序方式为选择排序和归并排序

---

正文

选择排序和归并排序是这次任务所选的两种排序方式

本文将介绍以下内容：

1. 计算运行时间
2. 比较二者运行时间
3. 根据运行时间作图

笔者所使用的书籍为《算法（第四版）》，所以有涉及到书籍中的API(StdRandom, Stopwatch, StdDraw)

1. 计算运行时间

归并排序

public static double timeTrial1(int N){
        int [] a = new int [N];
        for (int i = 0; i < N; i++) {
            a[i] = StdRandom.uniform(N);
        }
        Stopwatch timer = new Stopwatch();
        MergeSort.sort(a);
        return timer.elapsedTime();
    }

创建Stopwatch对象时开始及时，elapsedTime()方法返回自从创建对象到返回值之间所经过的时间（也就是排序运行的时间），单位为 s（秒）

选择排序

public static double timeTrial2(int N){
        double[] a = new double[N];
        for (int i = 0; i < N; i++) {
            a[i] = StdRandom.uniform(N);
        }
        Stopwatch timer = new Stopwatch();
        SelectionSort.sort(a);
        return timer.elapsedTime();
    }

采用的方法和上述相同

2. 比较二者运行时间

写一个测试数据(数据大小从200到204800），得出运行时间：

为了表示归并排序究竟比选择排序快多少，在for循环中加一行代码：

System.out.printf("\t\tMergeSort is %f times faster than SelectionSort\n",time2/time1);

数据量越大，就越能体现出差别

3. 根据运行时间作图

使用《算法》的API来进行作图

public static void Draw(){
        //set the size of canvas and set the Xscale and Yscale
        StdDraw.setCanvasSize(800,800);
        StdDraw.setXscale(0,13);
        StdDraw.setYscale(0,20);

        //draw the line as the Xscale and Yscale
        StdDraw.line(1,3,12.5,3);       //Xscale
        StdDraw.line(1,3,1,18.5);         //Yscale

        //set the radius of the points
        StdDraw.setPenRadius(0.01);

        //tell the difference about two kinds of points of the two Sort method
        StdDraw.text(2,19.5,"MergeSort");
        StdDraw.text(2,19,"SelectSort");
        StdDraw.setPenColor(Color.RED);
        StdDraw.point(3,19.5);
        StdDraw.setPenColor(Color.BLUE);
        StdDraw.point(3,19);

        //set the x_coordinate
        for (int i = 2, n = 200; i <= 12 ; n += n, i += 1) {
            StdDraw.text(1,2,String.valueOf(0));
            StdDraw.text(i,2,String.valueOf(n),45);
        }

        //set the y_coordinate
        for (int i = 4, n = 1; i < 19; n += 1,i++) {
            StdDraw.text(0.5,3,String.valueOf(0));
            StdDraw.text(0.5,i,String.valueOf(n/1.0));
        }

        //draw the points of the running time of MergeSort
        for (int N = 200, j = 1; N <= 204800; N += N, j++){
            StdDraw.setPenColor(Color.RED);
            Double time1 = timeTrial1(N);
            StdDraw.point(j+1, time1 + 3);
        }

        //draw the points of the running time of SelectSort
        for (int N = 200, j = 1; N <= 204800; N += N, j++){
            StdDraw.setPenColor(Color.BLUE);
            Double time2 = timeTrial2(N);
             StdDraw.point(j+1, time2 + 3);
        }
    }

会计算排序运行时间，并根据结果作图：

由此，排序的比较就暂且告一段落了，谢谢！