合并排序（看似随机重复）

Question

所以我的合并排序器代码有一个小错误，其中数组列表中的一些项目将被复制并扔到一个奇怪的位置

Sorted List    Unsorted List
apricot        gray
aqua           maize
bittersweet    mahogany
blue           green
brick          red
cornflower     apricot
flesh          bittersweet
gray           flesh
green          cornflower
lemon          orchid
magenta        pink
maize          orange
mahogany       maroon
bittersweet    blue
melon          yellow
orange         melon
orange         magenta
maroon         violet
blue           silver
pearl          tan
periwinkle     periwinkle
purple         turquoise
purple         thistle
olive          white
purple         sienna
tan            lemon
turquoise      pearl
brick          aqua
olive          brick
purple         olive
purple         purple

这是我编写的代码，感谢所有反馈：

ArrayList<String> a = new ArrayList<String>();

public MergeSorter(ArrayList<String> aList)
{
    a = aList;
}

public void sort()
{
    if (a.size() <= 1) return;
    ArrayList<String> first = new ArrayList<String>();
    ArrayList<String> second = new ArrayList<String>();
    for (int i = 0; i < a.size()/2; i++)
        first.add(a.get(i));
    for (int i = a.size()/2; i < a.size(); i++)
        second.add(a.get(i));
    MergeSorter firstSorter = new MergeSorter(first);
    MergeSorter secondSorter = new MergeSorter(second);
    firstSorter.sort();
    secondSorter.sort();
    merge(first, second);
}

private void merge(ArrayList<String> first, ArrayList<String> second)
{
    int iFirst = 0;
    int iSecond = 0;
    int j = 0;

    while(iFirst < first.size() && iSecond < second.size())
    {
        if(first.get(iFirst).compareTo(second.get(iSecond)) < 0)
        {
            a.set(j, first.get(iFirst));
            iFirst++;
        }
        else
        {
            a.set(j, second.get(iSecond));
            iSecond++;
        }
        j++;
    }
    //System.arraycopy(first, iFirst, a, j, first.size() - iFirst);
    for (int i = iFirst; i < first.size() - iFirst; i++)
    {
        a.set(j, first.get(i));
        j++;
    }

    //System.arraycopy(second, iSecond, a, j, second.size() - iSecond);
    for (int i = iSecond; i < second.size() - iSecond; i++)
    {
        a.set(j, second.get(i));
        j++;
    }

}

}

Answer 1

你迭代的不够远：

for (int i = iFirst; i < first.size() - iFirst; i++)
{
    a.set(j, first.get(i));
    j++;
}
for (int i = iSecond; i < second.size() - iSecond; i++)
{
    a.set(j, second.get(i));
    j++;
}

此时其中一个列表已经被完全消耗，您只需要将另一个列表的所有剩余元素复制到结果列表中即可。这意味着从 "the beginning of the end" (iFirst) 迭代到列表的末尾 (first.size()).

出于某种原因，您减去 iFirst，因此并非所有值都被复制。相反，未排序的值（用于初始化排序器的值）保留在列表的末尾，其中一些将与结果列表中实际排序的部分重复。

这应该有效：

for (int i = iFirst; i < first.size(); i++)
{
    a.set(j, first.get(i));
    j++;
}
for (int i = iSecond; i < second.size(); i++)
{
    a.set(j, second.get(i));
    j++;
}

合并排序（看似随机重复）

Merge Sorting (seemingly random duplications)

java

mergesort