合并排序实现 - 重复值错误

我想基于各种可用的在线教程实现合并排序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

来源

2015-12-02 Himanshu Verma

您不必重复值，有价值观被*覆盖*。即你的输入包含{1，-2}，这两者都在输出中丢失，而是有额外的3和8. – Draco18s

你merge方法是偶然在while循环的else情况下使用错误索引rightIn。这可能会导致覆盖值，表现为缺失值和重复值。

使用wholeIn类似于if的情况。变化

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

到

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

来源

2015-12-02 21:51:26 rgettman

啊愚蠢的错误。感谢您指出。 –

合并排序实现 - 重复值错误

回答

相关问题