为什么不能正确合并排序功能？

由于某种原因，此合并排序将无法正常运行。这几乎是正确的，但不完全。合并函数可以在我测试过的所有已排序数组上正常工作，并且mergeSort函数似乎没有任何明显的问题。我错过了什么？为什么不能正确合并排序功能？

示例输入：7,1,5,6,9,3,8,0,2,1。排序后，0 1 1 1 1 3 1 5 6 1。

每个后合并：

1 1 5 6 9 3 8 0 2 1 
1 1 5 6 9 3 8 0 2 1 
1 1 5 6 9 3 8 0 2 1 
1 1 5 6 9 3 8 0 2 1 
1 1 5 6 9 3 8 0 2 1 
1 1 5 6 9 0 3 0 2 1 
1 1 5 6 9 0 3 0 1 1 
1 1 5 6 9 0 1 1 3 1 
0 1 1 1 1 3 1 5 6 1

1000被添加到阵列，使得如果阵列具有不同的尺寸它们都总是完成没有发生错误的帽的端部。

void mergeSort(int arr[], int p, int r){ 
    if(p < r){ 
     int q = Math.floorDiv(p+r, 2); 
     mergeSort(arr,p,q); 
     mergeSort(arr,q+1,r); 
     merge(arr,p,q,r); 
    } 
} 

void merge(int arr[], int p, int q, int r){ 
    int n1 = q-p+1; 
    int n2 = r-q; 

    int merge1[] = new int[n1+1]; 
    int merge2[] = new int[n2+1]; 

    for(int i = 0; i<n1; i++) 
     merge1[i] = arr[p+i]; 
    for(int j = 0; j<n2; j++) 
     merge2[j] = arr[q+j+1]; 

    merge1[n1] = 1000; 
    merge2[n2] = 1000; 

    int i = 0; 
    int j = 0; 

    for(int k = p; k<r; k++){ 
     if(merge1[i] < merge2[j]){ 
      arr[k] = merge1[i]; 
      i++; 
     } else { 
      arr[k] = merge2[j]; 
      j++; 
     } 
    } 
}

来源

2017-01-23 Evan Weissburg

嗯，你通过调试代码加强，打印出每次迭代？ – OldProgrammer

是的，我将迭代添加到@OldProgrammer –

上，您可能需要查看基本情况，以了解何时不进行合并。我猜你的（arr，q + 1，r）迭代导致问题 – softwarenewbie7331

我想通了！这是merge函数的一个问题，在for(int k = p; k<r; k++){中。

基本上，r是数组中的最后一个索引。因此，通过迭代到数组的最后一个索引之前，我们每次都错过了最后一位数字。

更改>到>=

来源

2017-01-23 02:17:24

烨1个，有效recusive来电降低你的深度，这就是我怀疑。这应该指向了使用更具描述性的参数名称的重要性（而不是'p'和'r'），或Javadoc中说明如何调用一个方法，或（最好）两种。 – ajb

为什么不能正确合并排序功能？

回答

相关问题