你能检查一下我在 C 中实现递归归并排序函数时哪里出错了吗？

Question

我已经尝试了 3 天了，即使使用调试工具多次，我也找不到哪里出了问题。适用于大小为 2 的数组，但适用于大小为 6 的数组，输入为：55,34,76,12,45,76 我在排序后打印数组时得到不同的值，我的代码是这样的：

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
void sort(int arr[], int beg, int end);
void merg(int arr[], int beg, int mid, int end);
int main(void)
{
    int n = get_int("How many numbers? ");
    int* arr = malloc(sizeof(int)*n);
    for (int i = 0; i < n; i++)
    {
        printf("Enter %i Element of array: ", i + 1);
        arr[i] = get_int("");
    }
    sort(arr, 0, n-1);
    for (int i = 0; i < n; i++)
    {
        printf("%i   ", arr[i]);
    }
    printf("\n");
}
void sort(int arr[], int beg, int end)
{
    if (beg != end)
    {
        int mid = (beg + end) / 2;
        sort(arr, beg, mid);
        sort(arr + mid + 1, mid + 1, end);
        merg(arr, beg, mid, end);
    }
}
void merg(int arr[],int beg, int mid, int end)
{
    int sizel = mid - beg + 1;
    int sizer = end - mid;
    int* left = malloc(sizeof(int) * (sizel));
    int* right = malloc(sizeof(int) * sizer);
    for (int i = 0; i < sizel; i++)
    {
        left[i] = arr[beg + i];
    }
    for (int i = 0; i < sizer; i++)
    {
        right[i] = arr[mid + 1 + i];
    }

    int i = 0, j = 0, k = 0;
    for (k = 0; k <= end; k++)
    {
        if (i == sizel)
        {
            arr[k] = right[j];
            j++;
        }
        else if (j == sizer)
        {
            arr[k] = left[i];
            i++;
        }
        else
        {
            if (left[i] < right[j])
            {
                arr[k] = left[i];
                i++;
            }
            else
            {
                arr[k] = right [j];
                j++;
            }
        }
    }
    free(left);free(right);
    return;
}

Answer 1

你的主要问题是你混淆了符号。您可以通过 start, length 或 base, lo, hi.

来标识子范围

你有这个，其中一条线以一种方式做事，另一条线以另一种方式做事，但做得很糟糕：

    sort(arr, beg, mid);
    sort(arr + mid + 1, mid + 1, end);

你需要：

    sort(arr, beg, mid);
    sort(arr, mid + 1, end);

即始终使用 start, lo, hi 表示法。就目前而言，您是在告诉您的代码访问数组边界之外的很长一段路。这并不意味着您的程序会自动崩溃，但它确实会导致未定义的行为和错误的结果。

您应该创建一个 'dump array' 函数，例如：

static void dump_array(const char *tag, int size, const int data[size])
{
    printf("%s (%d):", tag, size);
    for (int i = 0; i < size; i++)
        printf(" %d", data[i]);
    putchar('\n');
}

这允许您在需要时打印数组。然后，在第一次递归调用 sort() 之后，您输入：

 dump_array("After 1st sub-sort", mid - beg + 1, &arr[beg]);

所以你可以看到你在那里得到了什么，第二次递归调用之后的另一个调用，以及 merg() 之后的第三次调用。你也可以在其他地方打印（进入功能也是一个不错的选择）。

在这种情况下，也许您应该对函数使用不同的设计：

static void dump_array(const char *tag, const int *data, int lo, int hi)
{
    printf("%s (%d:%d):", tag, lo, hi);
    for (int i = lo; i <= hi; i++)
        printf(" %d", data[i]);
    putchar('\n');
}

现在你可以写：

sort(arr, beg + 0, mid);
dump_array("After 1st sub-sort", arr, beg + 0, mid);
sort(arr, mid + 1, end);
dump_array("After 2nd sub-sort", arr, mid + 1, end);

工作代码

此代码对 merg() 函数进行了认真的修改，该函数中存在许多问题。它还添加了我推荐的工具。

#include <assert.h>
#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static void sort(int arr[], int beg, int end);
static void merg(int arr[], int beg, int mid, int end);
static void dump_array(const char *tag, const int *data, int lo, int hi);

int main(void)
{
    int n = get_int("How many numbers? ");
    int *arr = malloc(sizeof(int) * n);
    assert(arr != NULL);
    for (int i = 0; i < n; i++)
    {
        printf("Enter %i Element of array", i + 1);
        arr[i] = get_int(": ");
    }
    sort(arr, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
        printf("%i   ", arr[i]);
    }
    printf("\n");
}

static void sort(int arr[], int beg, int end)
{
    if (beg != end)
    {
        int mid = (beg + end) / 2;
        dump_array("-->> sort()", arr, beg, end);
        sort(arr, beg, mid);
        dump_array("After 1st sub-sort", arr, beg + 0, mid);
        sort(arr, mid + 1, end);
        dump_array("After 2nd sub-sort", arr, mid + 1, end);
        merg(arr, beg, mid, end);
        dump_array("<<-- sort()", arr, beg, end);
    }
}

static void merg(int arr[], int beg, int mid, int end)
{
    int sizel = mid - beg + 1;
    int sizer = end - mid;
    int *left = malloc(sizeof(int) * (sizel));
    int *right = malloc(sizeof(int) * sizer);
    assert(left != NULL && right != NULL);

    memcpy(left, arr + beg, sizel * sizeof(int));
    memcpy(right, arr + mid + 1, sizer * sizeof(int));

    int i = 0;
    int j = 0;
    int k = beg;
    while (i < sizel && j < sizer)
    {
        if (left[i] < right[j])
            arr[k++] = left[i++];
        else
            arr[k++] = right[j++];
    }
    /* Only one of these loop bodies executes */
    while (i < sizel)
        arr[k++] = left[i++];
    while (j < sizer)
        arr[k++] = right[j++];

    free(left);
    free(right);
}

static void dump_array(const char *tag, const int *data, int lo, int hi)
{
    printf("%s (%d:%d):", tag, lo, hi);
    for (int i = lo; i <= hi; i++)
        printf(" %d", data[i]);
    putchar('\n');
}

我用一个名为 data 的文件进行了测试，其中包含：

第一行，11，标识条目数；然后有 10 到 99 之间的 11 个随机数。运行 ms71 < data 的输出（忽略输入提示——这看起来很愚蠢，因为从文件中读取的数据没有回显），输出是：

-->> sort() (0:10): 19 66 71 69 91 46 14 38 77 97 34
-->> sort() (0:5): 19 66 71 69 91 46
-->> sort() (0:2): 19 66 71
-->> sort() (0:1): 19 66
After 1st sub-sort (0:0): 19
After 2nd sub-sort (1:1): 66
<<-- sort() (0:1): 19 66
After 1st sub-sort (0:1): 19 66
After 2nd sub-sort (2:2): 71
<<-- sort() (0:2): 19 66 71
After 1st sub-sort (0:2): 19 66 71
-->> sort() (3:5): 69 91 46
-->> sort() (3:4): 69 91
After 1st sub-sort (3:3): 69
After 2nd sub-sort (4:4): 91
<<-- sort() (3:4): 69 91
After 1st sub-sort (3:4): 69 91
After 2nd sub-sort (5:5): 46
<<-- sort() (3:5): 46 69 91
After 2nd sub-sort (3:5): 46 69 91
<<-- sort() (0:5): 19 46 66 69 71 91
After 1st sub-sort (0:5): 19 46 66 69 71 91
-->> sort() (6:10): 14 38 77 97 34
-->> sort() (6:8): 14 38 77
-->> sort() (6:7): 14 38
After 1st sub-sort (6:6): 14
After 2nd sub-sort (7:7): 38
<<-- sort() (6:7): 14 38
After 1st sub-sort (6:7): 14 38
After 2nd sub-sort (8:8): 77
<<-- sort() (6:8): 14 38 77
After 1st sub-sort (6:8): 14 38 77
-->> sort() (9:10): 97 34
After 1st sub-sort (9:9): 97
After 2nd sub-sort (10:10): 34
<<-- sort() (9:10): 34 97
After 2nd sub-sort (9:10): 34 97
<<-- sort() (6:10): 14 34 38 77 97
After 2nd sub-sort (6:10): 14 34 38 77 97
<<-- sort() (0:10): 14 19 34 38 46 66 69 71 77 91 97
14   19   34   38   46   66   69   71   77   91   97

当要排序的数组只有一个元素时，可能还有优化的空间，这样代码就不会递归。

你能检查一下我在 C 中实现递归归并排序函数时哪里出错了吗？

Can You check where I have my error in implementing Recursive merge sort function in C?

c

arrays

recursion

mergesort

cs50

工作代码