c++ - 使用数组而不是 vector 合并排序实现

Question

我正在尝试使用 arrays 而不是 vectors 来实现 merge-sort 算法，但我在其中遇到了一些错误我的两个功能。两个函数的代码如下。

void Merge(int ar[], int ar1[], int ar2[], int n1, int n2) {

    int p1 = 0;
    int p2 = 0;
    int p3 = 0;
    while (p1 < n1 && p2 < n2) {
        if (ar1[p1] < ar2[p2])
        {
            ar[p3]=ar1[p1];
            p3++;
            p1++;
        }
        else
        {
            ar[p3]=ar2[p2];
            p3++;
            p2++;
        }
    }

    while (p1 < n1)
    {
        ar[p3]=ar1[p1];
        p3++;
        p1++;
    }

    while (p2 < n2)
    {
        ar[p3]=ar2[p2];
        p3++;
        p2++;
    }
}

---

我想出了如何用下面的代码解决我所面临的问题。

void Sortmerge(int array[],int n) {

    if (n <= 1) return;

    if (n % 2 == 0)
    {
        int arr1[n/2];
        int arr2[n/2];
        int k=0;
        int l=0;

        for (int i=0;i<n;i++)
        {
            if (i<(n/2))
            {
                arr1[k++]=array[i];
            }

            else
            {
                arr2[l++]=array[i];
            }
        }

        Sortmerge(arr1,n/2);
        Sortmerge(arr2,n/2);

        for (int i=0;i<n;i++)
        {
        array[i]=0;
        }

        Merge(array, arr1, arr2,n/2,n/2);
    }

    if (n%2!=0)
    {
        int arr1[(n-1)/2];
        int arr2[(n+1)/2];
        int k=0;
        int l=0;
        for (int i=0;i<n;i++)
        {
            if (i<((n-1)/2))
            {
                arr1[k++]=array[i];
            }

            else
            {
                arr2[l++]=array[i];
            }
        }

        Sortmerge(arr1,(n-1)/2);
        Sortmerge(arr2,(n+1)/2);

        for (int i=0;i<n;i++)
        {
            array[i]=0;
        }

        Merge(array, arr1, arr2,(n-1)/2,(n+1)/2 );
    }
}

Answer 1

您已经声明了两组数组。两个名为 arr1 和两个名为 arr2。这些添加了一些数据，但随后它们超出了范围并且不使用数据。这就是警告的来源。

然后您尝试在它们的范围之外使用 arr1 和 arr2 - 在 if block 之外。这是错误的来源。这些数组必须声明一次，可能在您的函数 (Sortmerge) 的顶部，在您的 n % 2 检查之前。