正文之前
写了好几篇排序算法的文章，刚好碰上课程作业，需要比较一种慢排序和一种快排序的效率，所以《排序》系列文章中间就安排了这个小插曲，本文选取的排序方式为选择排序和归并排序
正文
本文将介绍以下内容：
- 计算运行时间
- 比较二者运行时间
- 根据运行时间作图
笔者所使用的书籍为《算法（第四版）》，所以有涉及到书籍中的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);
}
}
会计算排序运行时间，并根据结果作图：
由此，排序的比较就暂且告一段落了，谢谢！
