我写了一些java类来评估/演示不同的排序算法.但是当我运行我的演示类时,我感到困惑.希望你们能给我一个解释. (这个问题不是作业.)
首先,我列出一些与此问题相关的代码.
AbstractDemo
public abstract class AbstractDemo {
protected final int BIG_ARRAY_SIZE = 20000;
protected final int SMALL_ARRAY_SIZE = 14;
protected Stopwatch stopwatch = new Stopwatch();
public final void doDemo() {
prepareDemo();
specificDemo();
}
protected abstract void prepareDemo();
protected abstract void specificDemo();
protected final void printInfo(final String text) {
System.out.println(text);
}
}
SortingDemo
public class SortingDemo extends AbstractDemo {
private static final String FMT = "%-10s| %-21s| %7s ms.";
private static final String SPL = AlgUtil.lineSeparator('-',45);
private static final String SPLT = AlgUtil.lineSeparator('=',45);
private int[] data;
private final List
跑表
public class Stopwatch {
private boolean running;
private long startTime;
private long elapsedMillisec;
public void start() {
if (!running) {
this.startTime = System.currentTimeMillis();
running = true;
} else {
throw new IllegalStateException("the stopwatch is already running");
}
}
public void stop() {
if (running) {
elapsedMillisec = System.currentTimeMillis() - startTime;
running = false;
} else {
throw new IllegalStateException("the stopwatch is not running");
}
}
public void reset() {
elapsedMillisec = 0;
}
public long read() {
if (running) {
elapsedMillisec = System.currentTimeMillis() - startTime;
}
return this.elapsedMillisec;
}
}
生成随机数组的方法
public static int[] getRandomIntArray(final int len,final int max,boolean allowNegative) {
final int[] intArray = new int[len];
final Random rand = new Random();
rand.setSeed(20100102);
if (!allowNegative) {
if (max <= 0) {
throw new IllegalArgumentException("max must be possitive if allowNegative false");
}
for (int i = 0; i < intArray.length; i++) {
intArray[i] = rand.nextInt(max);
}
} else {
int n;
int i = 0;
while (i < len) {
n = rand.nextInt();
if (n < max) {
intArray[i] = n;
i++;
}
}
}
return intArray;
}
你可以看到,我生成了一个带有20000个元素的int数组.因为我在getRandomIntArray方法中有一个固定的种子,所以每次调用它时都会有相同的数组. SortingDemo类有main方法,如果我运行这个类,我得到输出：
Sorting 20000 elements
=============================================
O(n^2) | InsertionSort | 101 ms.
---------------------------------------------
O(n^2) | SelectionSort | 667 ms.
---------------------------------------------
O(n^2) | BubbleSort | 1320 ms.
---------------------------------------------
O(nlog(n))| MergeSort | 39 ms.
---------------------------------------------
O(?) | OptimizedMergeSort | 11 ms.
---------------------------------------------
看起来不错.现在有些让我感到困惑的事情.如果我在SortingDemo中更改demoList.add()序列,请说：
demoList.add(new InsertionSort());
demoList.add(new SelectionSort());
demoList.add(new BubbleSort());
// OptimizedMergeSort before Mergesort
demoList.add(new OptimizedMergeSort());
demoList.add(new MergeSort());
我有：
Sorting 20000 elements
=============================================
O(n^2) | InsertionSort | 103 ms.
---------------------------------------------
O(n^2) | SelectionSort | 676 ms.
---------------------------------------------
O(n^2) | BubbleSort | 1313 ms.
---------------------------------------------
O(?) | OptimizedMergeSort | 41 ms.
---------------------------------------------
O(nlog(n))| MergeSort | 14 ms.
---------------------------------------------
为什么输出与第一次运行不同？ OptimizedMergeSort花费的时间比普通MergeSort要长……
如果我在SortingDemo中取消注释for(int x = 1; x< 6; x)行,(使用相同的数组运行测试5次),我得到：
Sorting 20000 elements
=============================================
O(n^2) | InsertionSort | 101 ms.
---------------------------------------------
O(n^2) | SelectionSort | 668 ms.
---------------------------------------------
O(n^2) | BubbleSort | 1311 ms.
---------------------------------------------
O(?) | OptimizedMergeSort | 37 ms.
---------------------------------------------
O(nlog(n))| MergeSort | 10 ms.
---------------------------------------------
Sorting 20000 elements
=============================================
O(n^2) | InsertionSort | 94 ms.
---------------------------------------------
O(n^2) | SelectionSort | 665 ms.
---------------------------------------------
O(n^2) | BubbleSort | 1308 ms.
---------------------------------------------
O(?) | OptimizedMergeSort | 5 ms.
---------------------------------------------
O(nlog(n))| MergeSort | 7 ms.
---------------------------------------------
Sorting 20000 elements
=============================================
O(n^2) | InsertionSort | 116 ms.
---------------------------------------------
O(n^2) | SelectionSort | 318 ms.
---------------------------------------------
O(n^2) | BubbleSort | 969 ms.
---------------------------------------------
O(?) | OptimizedMergeSort | 5 ms.
---------------------------------------------
O(nlog(n))| MergeSort | 10 ms.
---------------------------------------------
Sorting 20000 elements
=============================================
O(n^2) | InsertionSort | 116 ms.
---------------------------------------------
O(n^2) | SelectionSort | 319 ms.
---------------------------------------------
O(n^2) | BubbleSort | 964 ms.
---------------------------------------------
O(?) | OptimizedMergeSort | 5 ms.
---------------------------------------------
O(nlog(n))| MergeSort | 5 ms.
---------------------------------------------
Sorting 20000 elements
=============================================
O(n^2) | InsertionSort | 116 ms.
---------------------------------------------
O(n^2) | SelectionSort | 320 ms.
---------------------------------------------
O(n^2) | BubbleSort | 963 ms.
---------------------------------------------
O(?) | OptimizedMergeSort | 4 ms.
---------------------------------------------
O(nlog(n))| MergeSort | 6 ms.
---------------------------------------------
对于其他排序,结果看起来合理.但是对于mergeSort,为什么第一次运行比以后花费更长的时间？ 37ms：OptimizedMergeSort为4ms.
我认为即使Optimized / MergeSort的实现错误,输出应该保持不变,为什么有时同一个方法调用需要更长的时间,有时更短的时间？
作为信息,所有那些* Sort类扩展了一个超级抽象类Sorting.它有一个抽象方法void sort(int [] data)
MergeSort有mergeSorting方法和merge()方法.
OptimizedMergeSort扩展MergeSort,并覆盖mergeSorting()方法,(因为当数组大小< = 7时,它将执行insertSort)并重用MergeSort类中的merge()方法.
感谢您阅读这篇长篇文章和代码.如果你们能给我一些解释,我感激不尽.
所有测试都在Linux下的Eclipse中完成.
