合併排序實現 - 重複值錯誤

Question

我想基於各種可用的在線教程實現合併排序Java，但是我的結果列表具有重複值。在經過很多調試之後，我仍然無法找出實施過程中出現的問題。 以下是代碼：

public ArrayList<Integer> mergeSort(ArrayList<Integer> whole) 
{ 
    ArrayList<Integer> left = new ArrayList<Integer>(); 
    ArrayList<Integer> right = new ArrayList<Integer>(); 
    int center; 
    if(whole.size() ==1) return whole; 

    else 
    { 
     center = whole.size()/2; 

     for(int i = 0; i < center; i++ ) 
     { 
      left.add(whole.get(i)); 
     } 
     for(int i = center ; i < whole.size(); i++ ) 
     { 
      right.add(whole.get(i)); 
     } 

     left = mergeSort(left); 
     right = mergeSort(right); 

     whole = merge(left, right, whole); 
    return whole; 
    } 


} 


private ArrayList<Integer> merge(ArrayList<Integer> left, ArrayList<Integer> right, ArrayList<Integer> whole) 
{ 
    // TODO Auto-generated method stub 

    int leftIn = 0; 
    int rightIn = 0; 
    int wholeIn = 0; 

    while(leftIn <left.size() && rightIn < right.size()) 
    { 
     if(left.get(leftIn).compareTo(right.get(rightIn)) < 0) 
     { 
      whole.set(wholeIn, left.get(leftIn)); 

      leftIn++; 
     } 
     else 
     { 
      whole.set(rightIn, right.get(rightIn)); 

      rightIn++; 
     } 
     wholeIn++; 
    } 

    ArrayList<Integer> rest; 
    int restIn; 
    if(leftIn >= left.size()) 
    { 
     rest = right; 
     restIn = rightIn; 
    } 
    else 
    { 
     rest = left; 
     restIn = leftIn; 
    } 

    for(int i = restIn ; i < rest.size(); i++) 
    {  
     whole.set(wholeIn, rest.get(i)); 
     wholeIn++; 
    } 
    return whole; 

} 

輸入列表：1 5 98 -2 -221 3 8 7

輸出：-221 3 7 8 5 3 8 98

Answer 1

你merge方法是偶然在while循環的else情況下使用錯誤索引rightIn。這可能會導致覆蓋值，表現爲缺失值和重複值。

使用wholeIn類似於if的情況。變化

whole.set(rightIn, right.get(rightIn)); 

到

whole.set(wholeIn, right.get(rightIn));