c - merge_sort算法中，参数为double类型list有效，int类型list无效

Question

我想对 int 类型列表进行排序。但是当合并函数中的参数是 double 列表时，它起作用了!但不是当它是 int list...

这里是排序函数。参数是int指针。

如果将 int 列表更改为 double 列表工作正常。

ex) int *a -> double *a

ex) int *l, *r1 -> double *l, *r1

ex) l = (int *)calloc(n1+1,sizeof(int)), r1 = (int *)calloc(n2+1,sizeof(int))-> l = (double *)calloc(n1+1,sizeof(double)) r1 = (double *)calloc(n2+1,sizeof(double))

void merge(int *a, int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q;
    int *l, *r1;
    int i, j, k;

    l = (int *)calloc(n1 + 1, sizeof(int));
    r1 = (int *)calloc(n2 + 1, sizeof(int));

    for (i = 0; i < n1;i++)
        l[i] = a[p + i];
    for (j = 0; j < n2; j++)
        r1[j] = a[q + 1 + j];

    l[n1] = 10000;
    r1[n2] = 10000;

    i = 0;
    j = 0;

    for (k = p; k <= r; k++) {
        if (l[i] <= r1[j]) {
            a[k] = l[i];
            ++i;
        } else {
            a[k] = r1[j];
            ++j;
        }
    }
    return;
}

这里是递归函数。直到列表的长度为1

ex) int *a -> double *a

void merge_sort(int *a, int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        merge_sort(a, p, q);
        merge_sort(a, q + 1, r);
        merge(a, p, q, r);
    }
}

创建一个长度为 10 的列表，并将其放入 mergesort 函数中。然后打印列表。

int main(int argc, char *argv[]) {

    int i, *a[10];

    for (i = 0; i < 10; i++) {
        a[i] = rand() % 10 + 1;  
    }

    merge_sort(a, 0, 10);

    for (i = 0; i < 10; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

结果是

0 0 0 2 5 10 9 9 3 5

Answer 1

您的代码中存在多个问题:

• 如果你想改变数组元素的类型，你必须在所有地方改变它，包括在main中。功能，您还必须更改 printf格式。提高警告级别 ( gcc -Wall -Wextra -Werror ) 可以防止愚蠢的错误。
• a 的定义在main不正确，应该是int a[10]; ，不是指向 int 的指针数组.
• 你将元素总数传递给mergesort()在main : merge_sort(a, 0, 10);这意味着 r在合并排序中应该被排除在外。递归调用 merge_sort(a, q + 1, r);在mergesort然后不正确为 q应排除在 merge_sort(a, p, q); 中但包括在下半场。使用 merge_sort(a, q, r);相反。
• 你用int q = (p + r) / 2;计算线段的中间.对于大数组，您可能有未定义的行为 q + r可能会溢出 int 类型的范围.这是一个典型的错误，可能会被忽视几十年，直到有人将代码用于大型数组。使用 int q = p + (r - p) / 2;避免它。
• merge 中的算法不正确:您假设数组中的所有值都是 < 10000 ，这可能是一个无效的假设。该代码应处理所有可能的值。您应该测试索引变量以检测子数组的结尾并专门处理另一个数组的剩余值。
• 你没有释放在merge中分配的数组，导致内存泄漏。
• 为了更容易更改元素类型，您可以使用 typedef .

这是一个改进的版本:

#include <stdio.h>

#ifdef USE_DOUBLE
typedef double sorttype;
#else
typedef int sorttype;
#endif

void merge(sorttype *a, int p, int q, int r) {
    // merge subarrays a[p...q] and a[q...r]
    // upper bounds q and r are excluded
    int n1 = q - p;
    int n2 = r - q;
    sorttype *a1, *a2;
    int i, j, k;

    a1 = malloc(n1 * sizeof(*a1));
    a2 = malloc(n2 * sizeof(*a2));

    for (i = 0; i < n1; i++)
        a1[i] = a[p + i];
    for (j = 0; j < n2; j++)
        a2[j] = a[q + j];

    i = 0;
    j = 0;
    for (k = p; k < r; k++) {
        if (i < n1 && (j >= n2 || a1[i] <= a2[j])) {
            a[k] = a1[i];
            ++i;
        } else {
            a[k] = a2[j];
            ++j;
        }
    }
    free(a1);
    free(a2);
}

void merge_sort(sorttype *s, int p, int r) {
    if (r - p > 1) {
        int q = p + (r - p) / 2;
        merge_sort(s, p, q);
        merge_sort(s, q, r);
        merge(s, p, q, r);
    }
}

int main(int argc, char *argv[]) {

    sorttype a[10];
    int i;

    for (i = 0; i < 10; i++) {
        a[i] = 1 + rand() % 10;
    }

    merge_sort(a, 0, 10);

    for (i = 0; i < 10; i++) {
#ifdef USE_DOUBLE
        printf("%g ", a[i]);
#else
        printf("%d ", a[i]);
#endif
    }
    printf("\n");
    return 0;
}

int 的输出:

1 3 4 4 5 8 9 9 10 10

Output for double:

1 3 4 4 5 8 9 9 10 10

Notice how the random numbers are identical although the program was recompiled and re-run... You should use srand(clock()) to try and get a different pseudo-random sequence.

Note also that allocating a2 to make a copy of the right subarray is not required because the merge operation never overwrites elements from the right half that have not already been copied.

Furthermore, you should test for allocation failure and report it.

Here is an improved version of merge:

void merge(sorttype *a, int p, int q, int r) {
    // merge subarrays a[p...q] and a[q...r]
    // upper bounds q and r are excluded
    int n1 = q - p;
    int n2 = r - q;
    sorttype *a1;
    int i, j, k;

    a1 = malloc(n1 * sizeof(*a1));
    if (a1 == NULL) {
        fprintf(stderr, "memory allocation failure\n");
        exit(1);
    }
    for (i = 0; i < n1; i++)
        a1[i] = a[p + i];

    i = 0;
    j = 0;
    for (k = p; i < n1 && k < r; k++) {
        if (j >= n2 || a1[i] <= a[q + j]) {
            a[k] = a1[i];
            ++i;
        } else {
            a[k] = a[q + j];
            ++j;
        }
    }
    free(a1);
}