合并排序Java合并排序代码不工作

Question

我们的老师给了我们合并排序的伪代码，如下所示

我想用Java实现它。我的代码如下：

public class MergeSorter {
/**
 * @param anArray
*/
    public MergeSorter(int[] anArray,int low, int high)
    {
        a = anArray;
        p = low;
        r = high;
    }
    public void sort()
    {
        if(p < r)
        {
           q = (p + r)/2;
           MergeSorter pqSorter = new MergeSorter(a, p, q);
           MergeSorter qrSorter = new MergeSorter(a, q + 1, r);
           pqSorter.sort();
           qrSorter.sort();
           merge(p, q, r);
        }
   }
private void merge(int low, int mid, int high)
{
   p = low;
   q = mid;
   r = high;
   int i;
   int j;
   int n1 = (q - p) + 1;
   int n2 = (r - q);
   int[] L = new int[n1+1];
   for (i = 0; i < n1; i++)
   {
       L[i] = a[(p + i)];
   }
   int[] R = new int[n2+1];
   for (j = 0; j < n2; j++)
       {
       R[j] = a[q + j];
       }
       L[n1] = Integer.MAX_VALUE;
       R[n2] = Integer.MAX_VALUE;
       i = 0;
       j = 0;
       for (int k = p; k < r; k++)
       {
           count = count + 1;
           if(L[i] <= R[j])
           {
               a[k] = L[i];
               i = i + 1;
           }
          else
           {
               a[k] = R[j];
               j = j + 1;
          }
       } 
    }
    private int[] a;
    private int p; 
    private int r;
    private int q;
    public int count = 0;
}

但这个代码不起作用。我想知道问题出在哪里。对不起，方向错了。 更新：这是我的其他代码。它现在给了一些东西，但排序不正确。 下面是我的测试代码

    public static void main(String[] args) throws FileNotFoundException, IOException
    {
      int[] a = {1,4,6,2,10,7};
      MergeSorter sorter = new MergeSorter(a,0,a.length);
      sorter.sort();
      System.out.println(Arrays.toString(a));
     }        

结果，它输出[1,2,4,4,2,7]

Answer 1

在q=（p+r）/2处的Sort函数中缺少floor函数。你说过你已经修好了。下一个问题是从main调用MergeSorter sorter = new MergeSorter(a,0,a.length);。我认为这是必然的。您的伪代码适用于第一个元素位于索引1的数组。但在java中，数组从索引0开始。在进行更改后，您需要在合并函数中调整两个小问题。祝你好运

Answer 2

我以前用C写过一个合并排序，效果很好。如果有什么事发生，试着比较一下

另外，检查索引，因为伪代码使用1.中的数组索引。。n编写代码时，C、Java等语言使用0作为第一个索引

#include <stdio.h>


int A[] = {11, 32 ,2, 7, 1, 15 };

void
merge_sort(int A[], int startIndex, int endIndex)
{
    int q = 0;
    //Terminating condition
    if (!(startIndex < endIndex)) {
       return; 
    }

    q = (startIndex + endIndex) / 2;
    merge_sort(A, startIndex, q);
    merge_sort(A, q+1, endIndex);
    printf("\n merge with start[%d], q[%d], end[%d]", startIndex,q, endIndex);
    merge(A, startIndex, q, endIndex);
}

merge(int A[], int startIndex, int q, int endIndex)
{
   int i = 0; int j = 0; int k=0;  
   int C[endIndex - startIndex + 1];
   int A1[q - startIndex + 1];
   int A2[endIndex - q];
   int lenA1 =q - startIndex + 1;
   int lenA2 = endIndex - q; 
   int iterator = 0;
   int lenA = endIndex - startIndex + 1;

   for(iterator = 0; iterator < lenA1; iterator++) {
      A1[iterator] = A[iterator + startIndex]; 
      printf("\n Iterator1[%d]", iterator + startIndex);
   }

    dump(A1, lenA1);
   for(iterator = 0; iterator < lenA2; iterator++) {
      A2[iterator] = A[iterator + q + 1]; 
      printf("\n Iterator2[%d]", iterator + q + 1);
   }

    dump(A2, lenA2);

   for (iterator = startIndex; iterator < (endIndex - startIndex + 1) && ((i < lenA1) && (j<lenA2)); iterator++)
   {
       if (A1[i] <= A2[j]) {
           A[k] = A1[i]; 
           printf("\n\t--A[k]--");
           k+=1;
           i+=1; 
       } else {
           A[k] = A2[j];
           printf("\n\t****A[k]***");
           j+=1; 
           k+=1;      
       }
   }
   if (j < lenA2) {
      for (iterator = j; iterator < lenA2; iterator++)
      {
           A[k] = A2[j];
           j+=1; 
           k+=1;      
      }
   } else if (i < lenA1) {
           A[k] = A1[i]; 
           k+=1;
           i+=1; 
   }
    dump(A, lenA);
    fflush(stdout);

}

void dump(int A[], int len)
{
    int i;
    printf("\n --------");
    for(i=0; i<len; i++)
    {
        printf("[%d] ", A[i]);
    }
}

int main()
{
    merge_sort(A, 0, 6);
    dump(A, 7);
//    dump(C, 7);
}

Answer 3

你有几个一个接一个的错误

MergeSorter sorter = new MergeSorter(a,0,a.length);

数组的最后一个索引是a.length - 1

for (j = 0; j < n2; j++)
{
    R[j] = a[q + j];
}

要合并的后半部分从索引q+1运行到r

for (int k = p; k < r; k++)

最后一个要填充的索引是r，而不是r-1，因此条件应该是k <= r

此外，实例变量的设置

p = low;
q = mid;
r = high;

在merge()中，鱼是腥味的。这并没有什么坏处，因为他们设定了他们已经拥有的价值观，但原则上这是错误的

Answer 4

您的代码与伪代码不完全对应 提示：索引

仅仅因为Java是面向对象的，并不意味着你必须在所有东西上使用对象。在这种情况下，没有它你会更好

public static void mergeSort(int[] array) {
    mergeSort(array, 0, array.length-1);
}

private static void mergeSort(int[] array, int p, int r) {
    ...
}

private static void merge(int[] array, int p, int q, int r) {
    ...
}