0

我正在尝试在 C 中实现合并排序算法。在递归数组拆分函数中，尽管有 return 语句，但我的基本情况会无限发生，并且永远不会调用合并函数。这是我的代码：

#include <stdio.h>

const int MAX = 1000;

int getArray(int unsorted[MAX], int upperBound)
{
    int i;
    for(i = 0; i <= upperBound; ++i)
    {
        printf("Now enter integer number %d: ", i + 1);
        scanf("%d", &unsorted[i]);
        while((getchar()) != '\n');
    }   
    printf("\n");
    return 0;
}

int merge(int unsorted[MAX], int sorted[1000], int lowerLeft, int lowerRight)
{
    if(lowerLeft == lowerRight)
        return 0;
    int j = lowerRight;
    for(int i = lowerLeft; i < lowerRight; ++i)
    {
        if(unsorted[i] <= unsorted[j])
        {
            sorted[i] = unsorted[i];
            ++j;
        }
        else
        {
            sorted[i] = unsorted[j];
            ++j;
        }
    }
    return 1;
}

int split(int unsorted[MAX], int sorted[1000], int lowerBound, int upperBound)
{
    printf("%d is the lBound and %d is the uBound\n", lowerBound, upperBound);
    if(lowerBound == upperBound)
    {
        printf("\nBase case triggered.");
        getchar();
        return 0;
    }
    int middle = upperBound/2;
    split(unsorted, sorted, 0, middle);
    split(unsorted, sorted, middle + 1, upperBound);    
    merge(unsorted, sorted, lowerBound, middle);
    return 1;
}

int main()
{
    int unsorted[MAX];
    int sorted[MAX];
    int lowerBound = 0;
    int upperBound;

    printf("First enter the number of integers you wish to sort: ");
    scanf("%d", &upperBound);
    while((getchar()) != '\n');
    printf("\n");
    upperBound = upperBound - 1;
    getArray(unsorted, upperBound);
    split(unsorted, sorted, lowerBound, upperBound);
    printf("\n");
    for(int c = 0; c < upperBound; ++c)
    {
        printf("%d, ", sorted[c]);
    }

    return 0;
}

为什么在达到基本情况后不会调用合并函数？对不起，如果我没有方便地表达这个问题，希望有人可以在这里帮助我，谢谢。

4

1 回答 1

1

您的基本案例正在被触发，因为这就是递归算法的工作方式。split()你一遍又一遍地调用，lowerBound 和 upperBound 之间的差距越来越小，所以最终你的基本情况会被触发。这应该是一件好事，因为触发基本情况可以让您知道您的输入“数组”（单例）已排序并且可以合并。

它“立即”被触发的原因是它必须：不断调用 split() 直到满足基本情况，因此您将看到的第一个打印语句是基本情况。

于 2020-01-25T00:40:00.670 回答