java中的递归mergesort的小捻

-3

我想在java中编写mergesort程序。不幸的是，我的实现给出了一个零列表作为代码的结果。我无法找到这个问题，因为一切都看起来符合逻辑，并且对我来说是正确的。如果有人能帮我找到这个问题，我将不胜感激。java中的递归mergesort的小捻

的代码如下：

package com.company; 

public class Main { 

public static void main(String[] args) { 
    int[] array = {35,43,21,4,23,1,13,44}; 

    System.out.println("initial array is equal to:"); 
    for (int data:array) { 
     System.out.println(data); 
    } 
    mergeSort(array, new int[array.length], 0, array.length-1); 
    System.out.println("Sorted array is equal to: "); 
    for (int s:array) { 
     System.out.println(s); 
    } 
    // arr = {35,43,21,4,23,1,13,44} 
} 

public static void mergeSort(int[] array,int[] secondaryArray,int leftStart, int rightEnd){ 
    if(leftStart >= rightEnd){ 
     return; 
    } 
    int midPoint = (leftStart + rightEnd)/2; 
    //sorting the left array 
    mergeSort(array, secondaryArray, leftStart, midPoint); 
    //sorting the right array 
    mergeSort(array, secondaryArray, midPoint+1, rightEnd); 
    //merging the sorted left and right array 
    mergeHalves(array, secondaryArray,leftStart, rightEnd); 
} 

public static void mergeHalves(int[] array, int[] secondaryArray, int leftStart, int rightEnd){ 

    int leftEnd = (leftStart + rightEnd)/2; 
    int rightStart = leftEnd + 1; 
    int index = 0; 

    while ((leftStart <= leftEnd) && (rightStart <= rightEnd)){ 
     if(array[leftStart] <= array[rightStart]){ 
      secondaryArray[index] = array[leftStart]; 
      leftStart++; 
     }else { 
      secondaryArray[index] = array[rightStart]; 
      rightStart++; 
     } 
     index++; 
    } 

    System.arraycopy(array,rightStart,secondaryArray,index,rightEnd-rightStart+1); 
    System.arraycopy(array,leftStart,secondaryArray,index,leftEnd-leftStart+1); 
    System.arraycopy(secondaryArray,0,array,0,secondaryArray.length); 

} 
}

来源

2017-08-13 user4353393

你应该做一些调试。 –

您在mergeHalves有一个小bug-，最终阵列副本

System.arraycopy(secondaryArray,0,array,0,secondaryArray.length);

时，应当（假设leftStartCopy是leftStart的副本中mergeHalves不变）：

System.arraycopy(secondaryArray,0,array,leftStartCopy,rightEnd-leftStartCopy+1);

问题是，您正在将所有secondaryArray复制到array，而不是仅相关的单元格。这就是导致array满了0的原因。

这里是mergeHalves的全码：

public static void mergeHalves(int[] array, int[] secondaryArray, int leftStart, int rightEnd){ 
int leftStartCopy = leftStart; 
int leftEnd = (leftStart + rightEnd)/2; 
int rightStart = leftEnd + 1; 
int index = 0; 

while ((leftStart <= leftEnd) && (rightStart <= rightEnd)){ 
    if(array[leftStart] <= array[rightStart]){ 
     secondaryArray[index] = array[leftStart]; 
     leftStart++; 
    }else { 
     secondaryArray[index] = array[rightStart]; 
     rightStart++; 
    } 
    index++; 
} 

System.arraycopy(array,rightStart,secondaryArray,index,rightEnd-rightStart+1); 
System.arraycopy(array,leftStart,secondaryArray,index,leftEnd-leftStart+1); 
System.arraycopy(secondaryArray,0,array,leftStartCopy,rightEnd-leftStartCopy+1);}

来源

2017-08-13 12:38:17

leftStart等于零，不是吗？如果它是真的，那么顺便写零或者leftStart – user4353393

并不重要，我试着实现你提到的，但是我再次去了0 – user4353393

不，leftStart是每次mergeHalves被调用时都是不同的（合并点的排序是每次处理数组的不同部分）。此外，leftStart在mergeHalves执行过程中发生更改。 –

尝试运行与控制你，看看你会得到什么样的投入每一个部分。例如，使用不同的输入数组运行mergeHalves，看看你是否能得到你所期望的。

你可以做的另一件事是让mergeHalves每次打印它的输入和最终结果。然后用小样本调用mergeSort（空数组，具有1个元素的数组，具有2个元素的数组等等），你很快就会明白你的代码实际上在做什么。

来源

2017-08-13 11:55:00 orip

java中的递归mergesort的小捻

回答

相关问题