Java 合并排序的实现；找不到错误

Question

好的，这是那些令人绝望的问题之一。我正在尝试实现自下而上的 MS 来排序和整数数组。但是天哪，我似乎找不到错误...

import java.util.Scanner;

public class A2 {

    public static boolean less(Integer v, Integer w) {
        return v.compareTo(w) < 0;
    }

    public static void sort(int[] a) {
        int N = a.length;
        int[] aux = new int[N];
        for (int sz = 1; sz < N; sz = sz + sz)
            for (int lo = 0; lo < N - sz; lo += sz + sz)
                merge(a, aux, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
    }

    public static void merge(int[] a, int aux[], int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;

        for (int k = lo; k <= hi; k++)
            aux[k] = a[k];

        for (int k = lo; k <= hi; k++) 
            if (i > mid)
                a[k] = aux[j++];
            else if (j > hi)
                a[k] = aux[i++];
            else if (less(aux[j], aux[i]))
                a[k] = a[j++];
            else
                a[k] = a[i++];

    }

    public static void main(String[] args) {
        int next = 0;
        Scanner scanner = new Scanner(System.in);
        int size = Integer.parseInt(scanner.nextLine());
        int[] v = new int[size];
        String s = scanner.nextLine();
        scanner.close();
        String[] sa = s.split("[\s]+");
        while (next < size) {
            v[next] = Integer.parseInt(sa[next]);
            next ++;
        }
        for (Integer i : v)
            System.out.print(i + " ");
        System.out.println();
        System.out.println("----------------------------------");
        sort(v);
        for (int i = 0; i < size; i++)
            System.out.print(v[i] + " ");
        System.out.println();
    }
}

在main函数中，我打印了数组的元素，只是为了确定问题出在排序上。第一个数字只是数组的大小。该错误在 sort() 或 merge() 中。这是一些示例输出：

9
10 45 20 5 -6 80 99 -4 0
10 45 20 5 -6 80 99 -4 0 
----------------------------------
-6 -4 -4 -6 -4 -4 -6 0 99 

6
6 7 3 2 4 1
6 7 3 2 4 1 
----------------------------------
1 1 1 4 6 7 

5
6 5 2 3 4
6 5 2 3 4 
----------------------------------
2 3 4 5 6

最后一个看起来还不错。

请帮帮我，我找了又找，似乎找不到错误。

Answer 1

您可以尝试使用此代码：

import java.util.Arrays;

public class MergeSort
{
   public static void merge(double[] a, 
                            int iLeft, int iMiddle, int iRight, 
                            double[] tmp)
   {
      int i, j, k;

      i = iLeft;
      j = iMiddle;
      k = iLeft;

      while ( i < iMiddle || j < iRight )
      {
         if ( i < iMiddle && j < iRight )
         {  // Both array have elements
            if ( a[i] < a[j] )
               tmp[k++] = a[i++];
            else
               tmp[k++] = a[j++];
         }
         else if ( i == iMiddle )
            tmp[k++] = a[j++];     // a is empty
         else if ( j == iRight )
            tmp[k++] = a[i++];     // b is empty
      }

      /* =================================
         Copy tmp[] back to a[]
         ================================= */
      for ( i = iLeft; i < iRight; i++ )
         a[i] = tmp[i];
   }

   public static void sort(double[] a, double[] tmp)
   {
      int width;

      for ( width = 1; width < a.length; width = 2*width )
      {
         // Combine sections of array a of width "width"
         int i;

         for ( i = 0; i < a.length; i = i + 2*width )
         {
            int left, middle, right;

        left = i;
        middle = i + width;
        right  = i + 2*width;

            merge( a, left, middle, right, tmp );

         }

         System.out.println("After 1 iter: " + Arrays.toString(a) );
      }
   }
}

Answer 2

通过此更改，它可以在我的系统上运行。

            else if(less(aux[j], aux[i]))
                a[k] = aux[j++];             // fix  (aux)
            else
                a[k] = aux[i++];             // fix  (aux)

如果合并排序通过改变每次传递的合并方向来避免复制步骤，如果在合并传递结束时留下一个运行，则需要复制它。这个答案的第 3 部分有一个例子。

当我使用具有随机值的较大数组（如 800 万个整数）进行测试时，less(...) 的使用间歇性地使我系统上的运行时间加倍。将 if(less(aux[j], aux[i])) 更改为 if(aux[j] < aux[i]) 似乎已解决此问题或使其变得非常罕见。

更有效的合并排序的示例代码，它避免了复制，除非有奇数次通过。这可以通过先计算遍数来避免，如果遍数是奇数，就原地交换。这可以通过在初始遍历中对 32 或 64 个元素的组使用插入排序扩展到更大的子组。

    public static void sort(int[] a) {
        int n = a.length;
        if(n < 2)
            return;
        int[] dst = new int[n];
        int[] src = a;
        int[] tmp;
        for(int sz = 1; sz < n; sz = sz+sz){
            int lo;
            int md;
            int hi = 0;
            while(hi < n){
                lo = hi;
                md = lo+sz;
                if(md >= n){            // if single run remaining, copy it
                    System.arraycopy(src, lo, dst, lo, n-lo);
                    break;
                }
                hi = md+sz;
                if(hi > n)
                    hi = n;
                merge(src, dst, lo, md, hi);
            }
            tmp = src;                  // swap references
            src = dst;                  //  to change direction of merge
            dst = tmp;
        }
        if(src != a)                    // copy back to a if needed
            System.arraycopy(src, 0, a, 0, n);
    }

    public static void merge(int[] src, int[] dst, int lo, int md, int hi) {
        int i = lo;
        int j = md;
        int k = lo;
        while(true){
            if(src[j]< src[i]){
                dst[k++] = src[j++];
                if(j < hi)
                    continue;
                System.arraycopy(src, i, dst, k, md-i);
                return;
            } else {
                dst[k++] = src[i++];
                if(i < md)
                    continue;
                System.arraycopy(src, j, dst, k, hi-j);
                return;
            }
        }
    }

Answer 3

问题出在 merge() 方法中：在循环的最后 2 种情况下，您从 a 而不是 aux 复制值。当您复制 a[j++] 时没有问题，但当您复制 a[i++] 时，该值可能已被覆盖。

考虑到右片的值是复制后才写入的，所以只需要保存左片即可。

这是一个经过简化的修改版本：

    public static void merge(int[] a, int aux[], int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;

        for (int k = lo; k <= mid; k++)  // save a[lo..mid] to aux
            aux[k] = a[k];

        for (int k = lo; k <= hi; k++) {
            if (i > mid)
                a[k] = a[j++];
            else if (j > hi)
                a[k] = aux[i++];
            else if (less(a[j], aux[i]))
                a[k] = a[j++];
            else
                a[k] = aux[i++];
        }
    }

请注意，将 mid 视为右切片的开始，将 hi 视为切片末尾后的索引，这样会更不容易出错。 sort() 循环会更简单，无需棘手的 +/-1 调整。顺便说一句，您的版本中的内部循环测试被关闭了一个，尽管除了效率低下之外没有其他后果。应该是：

for (int lo = 0; lo < N - sz - 1; lo += sz + sz)

这是一个进一步简化的实现，其中包含 included/excluded 个切片和一个组合测试：

    public static void sort(int[] a) {
        int N = a.length;
        int[] aux = new int[N];
        for (int sz = 1; sz < N; sz = sz + sz)
            for (int lo = 0; lo < N - sz; lo += sz + sz)
                merge(a, aux, lo, lo + sz, Math.min(lo + sz + sz, N));
    }

    public static void merge(int[] a, int aux[], int lo, int mid, int hi) {
        for (int i = lo; i < mid; i++) { // save a[lo..mid[ to aux
            aux[i] = a[i];
        }
        for (int i = lo, j = mid, k = lo; i < mid; k++) {
            if (j < hi && less(a[j], aux[i]))
                a[k] = a[j++];
            else
                a[k] = aux[i++];
        }
    }

这个版本非常简单，但在大型数组上仍然不是很有效，因为每次传递都经过整个数组，破坏了处理器缓存方案。使用一堆大小递增的已排序子数组，以增量方式执行自下而上的合并会更有效。

Java 合并排序的实现；找不到错误

Java implementation of MergeSort; cannot find the bug

java

sorting

algorithm

debugging

mergesort