使用具有 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 与只有一个向量作为参数 ( Merge2 (int v[], int left, int m, int right) ) 的 Merge 函数一起使用，如果将我的行 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为the length of the vector，左边部分的范围为index l to index m，所以左边部分的长度为m-l+1，右边部分的范围为index m+1 to index 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);
}

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

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

Merge-sort using a merge function that has 2 arrays as parameters

c++

arrays

sorting

merge

mergesort