爲什麼不能正確合併排序功能？

由於某種原因，此合併排序將無法正常運行。這幾乎是正確的，但不完全。合併函數可以在我測試過的所有已排序數組上正常工作，並且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

爲什麼不能正確合併排序功能？

回答

相關問題