算法有时有效,有时无效。我正在使用此处找到的 JUnit 测试 http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html#mergesort_test
感谢您的帮助。
Java代码
package sorting;
public class MergeSort {
public static int[] sort(int[] A) {
mergeSortHelper(A, new int[A.length], 0, A.length - 1);
return A;
}
private static void mergeSortHelper(int[] A, int[] helper, int p, int r) {
if (p < r) {
int mid = (p + r)/2;
mergeSortHelper(A, helper, p, mid);
mergeSortHelper(A, helper, mid + 1, r);
merge(A, helper, p, mid, r);
}
}
private static void merge(int A[], int[] helper, int p, int q, int r) {
for (int i = p; i <= r; i++) {
helper[i] = A[i];
}
int j = p;
int k = q + 1;
int count = 0;
while (j <= q && k <= r) {
if (helper[j] <= helper[k]) {
A[p+count] = helper[j++];
} else {
A[p+count] = helper[k++];
}
count++;
}
while (j <= q) {
A[p+count] = A[j++];
count++;
}
while (k <= r) {
A[p+count] = A[k++];
count++;
}
}
}
JUnit
package tests;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;
import java.util.Arrays;
import java.util.Random;
import org.junit.Before;
import org.junit.Test;
import sorting.MergeSort;
public class MergeSortTest {
private int[] numbers;
private final static int SIZE = 7;
private final static int MAX = 20;
@Before
public void setUp() throws Exception {
numbers = new int[SIZE];
Random generator = new Random();
for (int i = 0; i < numbers.length; i++) {
numbers[i] = generator.nextInt(MAX);
}
}
@Test
public void testMergeSort() {
long startTime = System.currentTimeMillis();
MergeSort.sort(numbers);
long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println("Mergesort " + elapsedTime);
for (int i = 0; i < numbers.length - 1; i++) {
if (numbers[i] > numbers[i + 1]) {
fail("Should not happen");
}
}
assertTrue(true);
}
@Test
public void itWorksRepeatably() {
for (int i = 0; i < 200; i++) {
numbers = new int[SIZE];
Random generator = new Random();
for (int a = 0; a < numbers.length; a++) {
numbers[a] = generator.nextInt(MAX);
}
MergeSort.sort(numbers);
for (int j = 0; j < numbers.length - 1; j++) {
if (numbers[j] > numbers[j + 1]) {
fail("Should not happen");
}
}
assertTrue(true);
}
}
@Test
public void testStandardSort() {
long startTime = System.currentTimeMillis();
Arrays.sort(numbers);
long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println("Standard Java sort " + elapsedTime);
for (int i = 0; i < numbers.length - 1; i++) {
if (numbers[i] > numbers[i + 1]) {
fail("Should not happen");
}
}
assertTrue(true);
}
}
最佳答案
错误:
while (j <= q) {
A[p+count] = A[j++];
count++;
}
while (k <= r) {
A[p+count] = A[k++];
count++;
}
更正:
while (j <= q) {
A[p+count] = helper[j++];
count++;
}
while (k <= r) {
A[p+count] = helper[k++];
count++;
}
关于java - 不确定为什么 Java mergesort 算法偶尔会失败,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35621061/