Java 归并排序

我正在尝试创建一个合并排序方法，但它不断给出错误的排序。我在哪里可以更改以使其真正对数组进行排序？代码的哪一部分必须不同？感谢您的时间。

  public static void mergeSort(int[] array, int left,  int lHigh, int right, int rHigh) {  
        int elements = (rHigh - lHigh +1) ;  
        int[] temp = new int[elements];
        int num = left;
      while ((left <= lHigh) && (right <= rHigh)){
       if (a[left] <= array[right]) {
          temp[num] = array[left];
          left++;
        }
        else {
          temp[num] = array[right];
          right++;
        }
       num++;   
      }
     while (left <= right){
        temp[num] = array[left]; // I'm getting an exception here, and is it because of the num???
        left += 1;
        num += 1;  
     }  
     while (right <= rHigh) {
        temp[num] = array[right];
        right += 1;
        num += 1;  
     }  
     for (int i=0; i < elements; i++){
       array[rHigh] = temp[rHigh];
       rHigh -= 1;   
     }

编辑：现在 mergeSort 并没有真正对数字进行排序，有人可以告诉我它具体在哪里吗？特别是当我打印“测试合并排序”部分时。

首先，我假设这是学术性的而不是实用性的，因为您没有使用内置的排序函数。话虽这么说，这里有一些帮助您朝着正确的方向前进：

通常，可以将合并排序视为两种不同的方法：一种将两个排序列表合并为一个排序列表的 merge() 函数，以及一种递归地将列表分解为单个元素列表的 mergeSort() 函数。由于单个元素列表已经排序，因此您可以将所有列表合并到一个大的排序列表中。

这是一些临时的伪代码：

merge(A, B):
  C = empty list

  While A and B are not empty:
    If the first element of A is smaller than the first element of B:
      Remove first element of A.
      Add it to the end of C.
    Otherwise:
      Remove first element of B.
      Add it to the end of C.

  If A or B still contains elements, add them to the end of C.

mergeSort(A):
  if length of A is 1:
    return A

  Split A into two lists, L and R.

  Q = merge(mergeSort(L), mergeSort(R))

  return Q

也许这会帮助你明确你想去的地方。

如果没有的话，总有归并排序 http://en.wikipedia.org/wiki/Merge_sort在维基百科。

额外的:

为了帮助您，这里有一些代码中内嵌的注释。

  public static void mergeSort(int[] array, int left,  int lHigh, int right, int rHigh) {   
        // what do lHigh and rHigh represent?

        int elements = (rHigh - lHigh +1) ;     
        int[] temp = new int[elements];
        int num = left;

      // what does this while loop do **conceptually**? 
      while ((left <= lHigh) && (right <= rHigh)){
       if (a[left] <= a[right]) {
          // where is 'pos' declared or defined?
          temp[pos] = a[left];
          // where is leftLow declared or defined? Did you mean 'left' instead?
          leftLow ++;
        }
        else {
          temp[num] = a[right];
          right ++;
        }
       num++;   
      }

     // what does this while loop do **conceptually**?
     while (left <= right){
        // At this point, what is the value of 'num'?
        temp[num] = a[left];
        left += 1;
        num += 1;   
     }
     while (right <= rHigh) {
        temp[num] = a[right];
        right += 1;
        num += 1;       
     }
     // Maybe you meant a[i] = temp[i]?
     for (int i=0; i < elements; i++){
       // what happens if rHigh is less than elements at this point? Could
       // rHigh ever become negative? This would be a runtime error if it did
       a[rHigh] = temp[rHigh];
       rHigh -= 1;      
     }

我故意含糊其辞，以便您考虑算法。尝试将您自己的注释插入到代码中。如果你能写出概念上发生的事情，那么你可能不需要 Stack Overflow :)

我的想法是你没有正确实施这一点。这是因为看起来您只接触了数组的元素一次（或接近一次）。这意味着最坏的情况是O(N) http://en.wikipedia.org/wiki/Big_O_notation排序一般至少需要O(N * log N)据我所知，合并排序的更简单版本实际上是O(N^2).

More:

在合并排序的最简单实现中，我希望看到某种递归 http://en.wikipedia.org/wiki/Recursion#Recursion_in_computer_science在 mergeSort() 方法中。这是因为合并排序通常是递归定义的。有多种方法可以使用 for 和 while 循环迭代地完成此操作，但我绝对不推荐将其作为学习工具，除非您递归地获得它。

老实说，我建议采用我的伪代码或您在维基百科文章中找到的伪代码来实现此目的并重新开始您的代码。如果您这样做后仍然无法正常工作，请将其发布在这里，我们将帮助您解决问题。

Cheers!

最后：

  // Precondition: array[left..lHigh] is sorted and array[right...rHigh] is sorted.
  // Postcondition: array[left..rHigh] contains the same elements of the above parts, sorted.
  public static void mergeSort(int[] array, int left,  int lHigh, int right, int rHigh) {   
        // temp[] needs to be as large as the number of elements you're sorting (not half!)
        //int elements = (rHigh - lHigh +1) ;
        int elements = rHigh - left;

        int[] temp = new int[elements];

        // this is your index into the temp array
        int num = left;

        // now you need to create indices into your two lists
        int iL = left;
        int iR = right;

        // Pseudo code... when you code this, make use of iR, iL, and num!
        while( temp is not full ) {
           if( left side is all used up ) {
             copy rest of right side in.
             make sure that at the end of this temp is full so the
               while loop quits.
           }
           else if ( right side is all used up) {
             copy rest of left side in.
             make sure that at the end of this temp is full so the
               while loop quits.
           }
           else if (array[iL] < array[iR]) { ... }
           else if (array[iL] >= array[iR]) { ... }
        }
 }