使用递归在 C 中合并排序

Question

这是我在 C 中的合并排序代码。我无法理解这里的问题所在。我对指针的了解并不多。 merge 函数接受 2 个数组并将它们合并。排序函数是一个递归函数，应该对数组进行排序。


int * merge(int *fir, int n, int *sec, int m){
    int res[m+n];
    int x=0, y=0;
    for(int i = 0; i < m+n; i++){
        if(*(fir+x)<=*(sec+y)){
            res[i] = *(fir+x);
            x++;
        }else{
            res[i] = *(sec+y);
            y++;
        }

    }
    return res;
}

int * sort(int A[], int n){
    if(n == 1){
        return A;
    }
    int mid = n/2;
    int AL[mid], AR[n-mid];
    for(int i = 0; i < mid; i++){
        AL[i] = A[i];
    }
    for(int i = 0; i < n-mid; i++){
        AR[i] = A[i+mid];
    }
    int *BL, *BR;
    BL = sort(AL, mid);
    BR = sort(AR, n-mid);
    return(merge(BL, mid, BR, n-mid));
}

int main(){
    int n;
    scanf("%d", &n);
    int A[n];
    for(int i = 0; i < n; i++){
        scanf("%d", &A[i]);
    }
    int *sortedArray;
    sortedArray = sort(A, n);
    for(int i = 0; i < n; i++){
        printf("%d ", *(sortedArray+i));
    }

    return 0;
}

这是输出

q8.c:16:9: warning: address of stack memory associated with local variable 'res' returned [-Wreturn-stack-address]
        return res;
               ^~~
1 warning generated.
7
23 12 56 67 11 99 97
97 32766 539779418 32767 -2002825496 32767 6 %```

Answer 1

这里有两个问题：首先，您将部分数组合并到一个临时本地数组中，该数组在您从 merge 中 return 之后越界。您 return 指向无效内存的指针。这就是警告的内容。

其次，合并时不检查是否读取超出部分数组的限制：访问fir时条件x < n必须为真，同样y < m 和 sec.

您还通过 return 指向排序或合并数组的第一个元素的指针造成混淆。这表明您创建新的排序和合并数组（这就是您在 merge 中尝试做的事情）。这对于垃圾收集的现代语言来说是可以的，但 C 不能那样工作。

在 C 中，如果您需要新内存，则必须先分配它，然后显式释放它。在像您这样的递归函数中，这很乏味，因为您只对最终排序的数组感兴趣，而不对中间结果感兴趣。因此，C 排序算法通常“就地”工作：在整个排序和元素交换过程中使用相同的内存。除非您在排序前制作副本，否则元素的原始顺序将丢失。

归并排序需要辅助内存。在您的例子中，您使用临时数组 AL 和 AR，它们是原始数组 A 内容的副本。现在当你合并时，你可以将 AL 和 AR 合并回 A.

因此，与其创建临时本地数组，不如传入 A 以便它可以填充排序后的元素：

void sort(int A[], int n)
{
    if (n > 1) {
        int mid = n / 2;
        int AL[mid], AR[n - mid];

        for (int i = 0; i < mid; i++) AL[i] = A[i];
        for (int i = 0; i < n - mid; i++) AR[i] = A[i + mid];
        
        sort(AL, mid);
        sort(AR, n - mid);
        
        merge(A, AL, mid, AR, n - mid);
    }
}

您的 merge 函数现在与您之前的函数非常相似，只是您将结果数组作为参数，并且在使用 [= 访问元素之前必须捕获越界情况26=].

void merge(int *res, const int *fir, int n, const int *sec, int m)
{
    int x = 0, y = 0;

    for(int i = 0; i < m + n; i++) {
        if      (x == n)            res[i] = sec[y++];
        else if (y == m)            res[i] = fir[x++];
        else if (fir[x] <= sec[y])  res[i] = fir[x++];
        else                        res[i] = sec[y++];
    }
}

使用递归在 C 中合并排序

Merge Sort in C using Recursion

c

sorting

recursion

mergesort