java - 不确定为什么 Java mergesort 算法偶尔会失败

Question

算法有时有效，有时无效。我正在使用此处找到的 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);
      }


}

Answer 1

错误:

    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++;
    }