-
Notifications
You must be signed in to change notification settings - Fork 1.5k
/
SortTestHelper.java
122 lines (95 loc) · 4.06 KB
/
SortTestHelper.java
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
package bobo.algo;
import java.lang.reflect.Method;
import java.lang.Class;
import java.util.*;
public class SortTestHelper {
// SortTestHelper不允许产生任何实例
private SortTestHelper(){}
// 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]
public static Integer[] generateRandomArray(int n, int rangeL, int rangeR) {
assert rangeL <= rangeR;
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++)
arr[i] = new Integer((int)(Math.random() * (rangeR - rangeL + 1) + rangeL));
return arr;
}
// 生成一个近乎有序的数组
// 首先生成一个含有[0...n-1]的完全有序数组, 之后随机交换swapTimes对数据
// swapTimes定义了数组的无序程度:
// swapTimes == 0 时, 数组完全有序
// swapTimes 越大, 数组越趋向于无序
public static Integer[] generateNearlyOrderedArray(int n, int swapTimes){
Integer[] arr = new Integer[n];
for( int i = 0 ; i < n ; i ++ )
arr[i] = new Integer(i);
for( int i = 0 ; i < swapTimes ; i ++ ){
int a = (int)(Math.random() * n);
int b = (int)(Math.random() * n);
int t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}
return arr;
}
// 打印arr数组的所有内容
public static void printArray(Object[] arr) {
for (int i = 0; i < arr.length; i++){
System.out.print( arr[i] );
System.out.print( ' ' );
}
System.out.println();
return;
}
// 判断arr数组是否有序
public static boolean isSorted(Comparable[] arr){
for( int i = 0 ; i < arr.length - 1 ; i ++ )
if( arr[i].compareTo(arr[i+1]) > 0 )
return false;
return true;
}
// 测试sortClassName所对应的排序算法排序arr数组所得到结果的正确性和算法运行时间
// 将算法的运行时间打印在控制台上
public static void testSort(String sortClassName, Comparable[] arr){
// 通过Java的反射机制,通过排序的类名,运行排序函数
try{
// 通过sortClassName获得排序函数的Class对象
Class sortClass = Class.forName(sortClassName);
// 通过排序函数的Class对象获得排序方法
Method sortMethod = sortClass.getMethod("sort",new Class[]{Comparable[].class});
// 排序参数只有一个,是可比较数组arr
Object[] params = new Object[]{arr};
long startTime = System.currentTimeMillis();
// 调用排序函数
sortMethod.invoke(null,params);
long endTime = System.currentTimeMillis();
assert isSorted( arr );
System.out.println( sortClass.getSimpleName()+ " : " + (endTime-startTime) + "ms" );
}
catch(Exception e){
e.printStackTrace();
}
}
// 测试sortClassName所对应的排序算法排序arr数组所得到结果的正确性和算法运行时间
// 将算法的运行时间以long类型返回, 单位为毫秒(ms)
public static long testSort2(String sortClassName, Comparable[] arr){
// 通过Java的反射机制,通过排序的类名,运行排序函数
try{
// 通过sortClassName获得排序函数的Class对象
Class sortClass = Class.forName(sortClassName);
// 通过排序函数的Class对象获得排序方法
Method sortMethod = sortClass.getMethod("sort",new Class[]{Comparable[].class});
// 排序参数只有一个,是可比较数组arr
Object[] params = new Object[]{arr};
long startTime = System.currentTimeMillis();
// 调用排序函数
sortMethod.invoke(null,params);
long endTime = System.currentTimeMillis();
assert isSorted( arr );
return endTime - startTime;
}
catch(Exception e){
e.printStackTrace();
}
return 0;
}
}