我遇到了麻烦归并到正确

工作至今，我有以下代码：我遇到了麻烦归并到正确

public class MergeSort { 
int[] theList; 
int counter; //required for analysis later 
double time; //required for analysis later 

MergeSort(int[] n){ 
    int len = n.length; 
    this.theList = mergeSort(n, 0, len); 
} 

int[] mergeSort(int[] n, int p, int r){ 
    if((p + 1)<r){ 
     int q = (r + p)/2; 
     mergeSort(n, p, q); 
     mergeSort(n, q+1, r); 
     merge(n, p, q, r); 
    } 
    return n; 

} 
public void merge(int[] input, int p, int q, int r){ 
    int lefti = q - p; 
    int righti = r - q; 
    int[] left = new int[lefti+1]; 
    int[] right = new int[righti+1]; 
    for(int i = 0; i < lefti; i++){ 
     this.counter++; 
     left[i] = input[p+i]; 
    } 
    for(int i = 0; i < righti; i++){ 
     this.counter++; 
     right[i] = input[q+i]; 
    } 
    left[left.length - 1] = 1000000; 
    right[right.length - 1] = 1000000; 
    int i = 0; 
    int j = 0; 
    for(int k = p; k < r; k++){ 
     this.counter++; 
     if(left[i] < right[j]){ 
      input[k] = left[i]; 
      i++; 
     } 
     else{ 
      input[k] = right[j]; 
      j++; 
     } 
    } 
}

}

我想我已经在这个一直盯着太long.I将不胜感激，如果有人将能够引导我朝着更好的方向发展。

现在，通过MergeSort（[9,8,7,6,5,4,3,2,1,0]）的输入，该列表等于[4,1,0,2,3,7 ，5,6,8,9]。

我很感谢任何我可能会收到的帮助。

来源

2013-04-02 Sam Welch

您是否尝试过使用调试器？ –

你的数组索引中的一些问题.......你可以参考任何像coreman这样的书。 –

它看起来像你需要一个base case为你的mergeSort方法。如果（p + 1）> = r，则对子数组进行排序（即，子数组的大小应为1或2，如果大小为1则不做任何操作，如果大小为2，则交换这两个值如果它们出现故障）

来源

2013-04-02 19:45:04

我遇到了麻烦归并到正确

回答

相关问题