合并排序Java

发布时间：2020-12-15 01:59:33 所属栏目：Java 来源：网络整理

导读：我正在尝试创建一个合并排序方法,但它继续给出错误的排序.我在哪里进行更改以使其实际排序数组？代码的哪一部分必须有所不同？感谢您的时间. public static void mergeSort(int[] array,int left,int lHigh,int right,int rHigh) { int elements = (rHigh -

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

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

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

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

额外：

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

public static void mergeSort(int[] array,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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!