c - 将 2 个已排序数组合并到一个新的已排序数组中不起作用。我究竟做错了什么？

Question

该函数将sorted1和sorted2合并到一个新的排序数组(结果)中。 90% 的情况下，此函数工作正常，但有时 1-2 个数字不在其应有的位置(大多数情况下，这些数字是最后一个数字)。

有人可以帮我找出我做错了什么吗？

void merge2(int *sorted1,int *sorted2,int *result,int K)
{   
    int i,j,k;
    i=j=k=0;

    while(i<K && j<K)
    {
        if(*(sorted1+i)>*(sorted2+j))
        {
            *(result+k)=*(sorted2+j);
            j++;
            k++;
            if(*(sorted1+i)<*(sorted2+j))
            {
                *(result+k)=*(sorted1+i);
                i++;
                k++;
            }
        }   
        else if(*(sorted1+i)<*(sorted2+j))
        {
            *(result+k)=*(sorted1+i);
            i++;
            k++;
            if(*(sorted1+i)>*(sorted2+j))
            {
                *(result+k)=*(sorted2+j);
                j++;
                k++;
            }                
        }
        else
        {
            *(result+k)=*(sorted1+i);
            k++;
            i++;
            *(result+k)=*(sorted2+j);
            k++;
            j++;
        }  
    }

    while(i<K)
    {
        *(result+k)=*(sorted1+i);
        i++;
        k++;
    }

    while(j<K)
    {
        *(result+k)=*(sorted1+j);
        j++;
        k++;
    }        
}

Answer 1

您使用i作为sorted1的计数器，j作为sorted2的计数器。当 i 到达 K 底部时，while 循环应该用排序 2 的剩余元素填充结果的其余部分，但是您用排序 1 中的元素填充它。这意味着无论哪个计数器首先击中 K，其余的都会用排序 1 填充，因此解决方法是:

while(j<K)
{
    *(result+k)=*(sorted2+j);  // This used to be sorted1
    j++;
    k++;
}

您提到错误大多数时候出现在末尾，这意味着还存在其他错误。如果您可以提供出现这种情况的数据集(错误不在最后)，我将通过修复来修改我的答案(假设我可以找到它)。

请注意，最里面的分支并不是绝对必要的。第一个循环正在执行的操作的伪代码:

1    if sorted1[i] > sorted2[j]:
2        result[k++] = sorted2[j++]
3        if sorted1[i] < sorted2[j]:
4            result[k++] = sorted1[i++] 
5    else if sorted1[i] < sorted2[j]:
6        result[k++] = sorted1[i++]
7        if sorted1[i] Z sorted2[j]:
8            result[k++] = sorted1[i++]
9    else
10       result[k++] = sorted1[i++]
11       result[k++] = sorted2[j++]

第 3 行和第 4 行执行的操作与第 5 行和第 6 行执行下一次循环迭代的操作相同，而第 7 行和第 8 行执行的操作与第 1 行和第 2 行执行的操作相同。您可以将其减少为:

1    if sorted1[i] > sorted2[j]:
2        result[k++] = sorted2[j++]
3    else if sorted1[i] < sorted2[j]:
4        result[k++] = sorted1[i++]
5    else
6        result[k++] = sorted1[i++]
7        result[k++] = sorted2[j++]

编辑:最后，请注意，通过将 i 和 j 与 K 进行比较，您的合并算法仅在排序 1 和排序 2 都是 K 个元素长的情况下才起作用。我认为这是我的答案中设计的，但对于更通用的解决方案，请传入两个数组的大小并将 i 和 j 与各自的对应项进行比较。