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

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 -2 98 -221 3 8 7

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

Answer 1

您的 merge 方法在 while 循环的 else 情况下不小心使用了错误的索引 rightIn。这可能会导致值被覆盖，表现为缺失值和重复值。

像 if 案例那样使用 wholeIn。变化

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

到

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

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

Merge Sort implementation - Duplicate values error

java

algorithm

arraylist

collections

mergesort