c++ - 使用具有 2 个数组作为参数的合并函数进行合并排序

Question

void Merge1(int v1[], int L1, int v2[], int L2) // L1 and L2 are the lenghts of the vector
{
    int v3[100],i,j, a1,a2;
    a1=a2=0;
    for (i = 0; i < L1 + L2; i++)
    {
        if(a1!=L1 && a2 !=L2)
        {
            if (v1[a1] < v2[a2])
            {
                v3[i] = v1[a1];
                a1++;
            }
            else
            {
                v3[i] = v2[a2];
                a2++;
            }
        }
        else if (a1==L1)
        {
             v3[i] = v2[a2];
                a2++;
        }
        else if (a2==L2)
        {
            v3[i] = v1[a1];
            a1++;
        }
    }
    for (i = 0; i < L1+L2; i++)
    {
        v1[i]=v3[i];
    }
}

这是我使用 2 个数组的合并函数。它似乎工作正常。

void MergeSort (int v[], int l, int r)
{
    if (l==r) return;
    int m = (l+r)/2;
    MergeSort (v, l, m);
    MergeSort (v, m+1, r);
    Merge1(v, m, v+m, r-m);
}

在 int main () 中，我使用 MergeSort(v,0,n-1)，对于这样的数组:

9 5 2 9 4 6 4 3 8 1 22 11 7 1

结果是

1 2 3 4 4 6 7 8 9 9 5 11 22 1

对于像这样的数组:

1 7 3 2 6 2 4 21 1 2

结果是

1 1 2 2 4 6 7 3 21 2

我不明白。它似乎只起作用一点。我知道通常情况下，MergeSort 与 Merge 函数一起使用，该函数只有一个 vector 作为参数( Merge2 (int v[], int left, int m, int right) )，如果您替换我的行 Merge1(v, m, v+m, r-m) 和 Merge2(v, l, m, r)，我的 MergeSort 函数就可以工作了。尽管我想使用我的函数 Merge1 或具有 2 个数组作为参数及其长度的函数。

Answer 1

注意 Merge1 函数调用 Merge1(v, m, v+m, r-m);，并引用函数声明:

void MergeSort (int v[], int l, int r)
{
    if (l==r) return;
    int m = (l+r)/2;
    MergeSort (v, l, m);
    MergeSort (v, m+1, r);
    Merge1(v, m, v+m, r-m);
}


void Merge1(int v1[], int L1, int v2[], int L2) // L1 and L2 are the lenghts of the vector

由于预期参数 L1 和 L2 是 vector 的长度，左边部分的范围是从索引 l 到索引 m，所以左边部分的长度是m-l+1，右边的部分从索引m+1到索引r，所以右边部分的长度是r-m .

综上所述，Merge1函数的实现是可以的，但是函数调用应该是Merge1(v+l, m-l+1, v+m+1, r-m);。所以MergeSort函数应该是:

void MergeSort (int v[], int l, int r)
{
    if (l==r) return;
    int m = (l+r)/2;
    MergeSort (v, l, m);
    MergeSort (v, m+1, r);
    Merge1(v+l, m-l+1, v+m+1, r-m);
}

修改后的代码已经在我的电脑上测试正常，看看它是否适用于你的数据。