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

Question

算法有时有效，有时无效。我正在使用此处 http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html#mergesort_test

中的 JUnit 测试

感谢您的帮助。

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

Answer 2

我修改了代码 :) 以通过测试，但我不确定它是否是 100% 安全的代码。使用它需要您自担风险。

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++] = helper[j++];            
        }

        while (k <= r) {
            A[p+count++] = helper[k++];            
        }
    }
}

这些是发生的变化

diff --git a/src/sorting/MergeSort.java b/src/sorting/MergeSort.java
index 0f5c8e4..dbf6689 100644
--- a/src/sorting/MergeSort.java
+++ b/src/sorting/MergeSort.java
@@ -35,7 +35,7 @@
         int count = 0;

         while (j <= q && k <= r) {
-            if (helper[j] <= helper[k]) {
+            if (helper[j] < helper[k]) {
                 A[p+count] = helper[j++]; 
             } else {
                 A[p+count] = helper[k++];
@@ -45,13 +45,11 @@
         }

         while (j <= q) {
-            A[p+count] = A[j++];
-            count++;
+            A[p+count++] = helper[j++];            
         }

         while (k <= r) {
-            A[p+count] = A[k++];
-            count++;
+            A[p+count++] = helper[k++];            
         }
     }
 }
\ No newline at end of file

Answer 3

// https://github.com/kangchen/SortAlgorithm

进口java.util.ArrayList；导入 java.util.List;

public final class MergeSort 实现 Runnable, Sort {

private List<Integer> list;
private List<Integer> temp = new ArrayList<Integer> ();
private long time = 0;
private boolean sortCompleted = false;

public MergeSort(List<Integer> item) {
    this.list = item;
    initializeTempList();
}   

public void run() {
    sort();
    System.out.println(this.toString());
}

private void initializeTempList() {
    for(int i=0; i<list.size(); i++) {
        temp.add(0);
    }
}
/*
 * Merge Sort Algorithm O(N*LOGN)
 */
public void sort() {
    long starttime = System.nanoTime();
    mergePartition(0, list.size()-1);
    long endtime = System.nanoTime();
    time = endtime - starttime;
    sortCompleted = true;
}

private void mergePartition(int low, int high) {

    if (low == high) return;
    else {
        int mid = (low + high) / 2;
        mergePartition(low, mid);
        mergePartition(mid+1, high);
        merge(low, mid+1, high);
    }
}

private void merge(int lowPtr, int midPtr, int highPtr) {
    int ci = 0;
    int ai = lowPtr;
    int mid = midPtr - 1;
    int bi = highPtr - ai + 1;

    while (lowPtr <= mid && midPtr <= highPtr) {
        if (list.get(lowPtr) < list.get(midPtr)) {
            temp.set(ci++, list.get(lowPtr++));
        }
        else {
            temp.set(ci++, list.get(midPtr++));
        }
    }

    /*
     * copy remaining sorted elements
     */
    while (lowPtr <= mid) {
        temp.set(ci++, list.get(lowPtr++));
    }

    /*
     * copy remaining sorted elements
     */
    while (midPtr <= highPtr) {
        temp.set(ci++, list.get(midPtr++));
    }

    /*
     * replace original elements with sorted elements
     */
     copy(ai, bi, temp);
}

private void copy(int from, int num, List<Integer> arrTemp) {
    for(int i=0; i<num; i++){
        list.set(from+i, arrTemp.get(i));
    }
}

public long getTime() {
    return time;
}

public String toString() {
    return "Merge sort is completed in " + getTime() + " nanoseconds";
}

private void swap(int x, int y) {
    int tmp = list.get(x);
    list.set(x, list.get(y));
    list.set(y, tmp);
}

public void reversedList() {
    int idx = list.size()/2;
    int high = list.size()-1;
    for(int low=0; low<idx; low++) {
        swap(low, high--);
    }
} 

public boolean isSortCompleted() {
    return sortCompleted;
}

}

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

Not sure why Java mergesort algorithm occasionally fails

java

sorting

algorithm

mergesort

Java代码

JUnit