合并排序Java

Question

我正在尝试创建一个合并排序方法,但它继续给出错误的排序.我在哪里进行更改以使其实际排序数组？代码的哪一部分必须有所不同？感谢您的时间.

  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没有真正排序数字,有人可以告诉我具体是什么？特别是当我打印"测试合并排序"部分时.

Answer 1

首先,我假设这是学术性的而不是实际的,因为你没有使用内置的排序功能.话虽如此,这里有一些帮助,让你朝着正确的方向前进:

通常,可以将合并排序视为两种不同的方法: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

也许这有助于清理你想去的地方.

如果没有,维基百科上总会有MergeSort.

附加:

为了帮助您,以下是您的代码内联的一些注释.

  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)排序通常至少需要,据O(N * log N)我所知,实际上更简单的合并排序版本O(N^2).

更多:

在合并排序的最简单实现中,我希望在mergeSort()方法中看到某种递归.这是因为合并排序通常是递归定义的.有一些方法可以使用for和while循环迭代地执行此操作,但在您递归获取之前,我绝对不建议将其作为学习工具.

老实说,我建议你在维基百科文章中找到我的伪代码或伪代码,以实现这一点并重新开始使用你的代码.如果你这样做并且它仍然无法正常工作,请在此处发布,我们将帮助您解决问题.

干杯!

最后:

  // 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]) { ... }
        }
 }