2

我正在尝试通过合并排序对数组进行排序，并在排序时删除我认为相等的元素。我递归地调用合并排序然后合并。

我到了这一点，发现a并且c是​​重复的。 

a b | c d

我根据某些标准确定我想要哪一个，然后选择 c。我增加右手计数器和左手计数器并比较b和d。说我选d，然后我选b。我希望我的最终列表只有元素

c d b

但是，正在发生的事情发生在下一次递归调用中，start并且end是 0 和 3，因此 d 在下一次调用时在数组中列出了两次。合并过程使用的数组是：

c d b d

这是代码。提前致谢。

private static void merge(int[] data, int start, int mid, int end)
{
    int firstCopied=0;
    int secondCopied=0;
    int index=0;
    int length=end-start+1;

    int[] temp = new int[end-start+1];
    int firstSize=mid-start+1;
    int secondSize=end-mid;

    while(firstCopied < firstSize && secondCopied < secondSize)
    {
        if(data[start+firstCopied] < data[mid+1+secondCopied])
        {
            temp[index++] = data[start+firstCopied];
            firstCopied++;
        }

        else if(data[start+firstCopied] > data[mid+1+secondCopied])
        {
            temp[index++] = data[mid+1+secondCopied];
            secondCopied++;
        }

        else if(data[start+firstCopied]==data[mid+1+secondCopied])
        {
            boolean result = PickOne();

            if(result)
            {
                temp[index++] = data[start+firstCopied];
            }
            else
            {
                temp[index++] = data[mid+1+secondCopied];
            }

            firstCopied++;
            secondCopied++;
            length--;
        }
    }
    while(firstCopied < firstSize)
    {
        temp[index++] = data[start+firstCopied];
        firstCopied++;
    }

    while(secondCopied < secondSize)
    {
        temp[index++] = data[mid+1+secondCopied];
        secondCopied++;
    }

    for(int i=0; i<length; i++)
    {
        data[start+i]=temp[i];
    }

}
4

3 回答 3

1

C++ 标准库的理念是使用能做好一件事的算法。最好遵循这种方法，因为它会产生更多可重用的代码。

例如，这是一个合并排序草图，然后调用std::unique

template<typename BiDirIt>
void merge_sort(BiDirIt first, BiDirIt last)
{
    auto const N = std::distance(first, last);
    if (N < 2) return;

    // sort each part individually, then merge back in-place
    auto middle = first + N / 2;
    merge_sort(first, middle);
    merge_sort(middle, last);
    std::inplace_merge(first, middle, last);
}    

int data[] = { /* your data */ };
merge_sort(std::begin(data), std::end(data));

auto it = std::unique(std::begin(data), std::end(data));
for (auto ut = std::begin(data); ut != it; ++ut) {
    // process unique data
}

如果您的数据在 astd::vector而不是 C 数组中，您也可以调用v.erase(v.begin(), it);以实际擦除非唯一数据。

于 2013-05-08T09:08:19.800 回答
0

您merge在概念上更改了数组的长度。但是实际上没有代码可以截断data。我建议您返回length（而不是void）并使用一些最终的后处理步骤将数据截断为最终长度，或者至少避免打印那些过去的元素。

于 2013-05-08T08:57:23.907 回答
0

首先确保 [start, mid] 和 [mid + 1, end] 中的元素已排序且唯一。否则，代码运行后将存在重复项。

于 2013-05-08T09:19:34.533 回答