c - mergesort : no errors and warnings when compile and link, 但输出不按顺序

Question

这个问题不太可能对任何 future 的访客有帮助；它只与一个较小的地理区域、一个特定的时间点或一个非常狭窄的情况相关，通常不适用于全世界的互联网受众。如需帮助使此问题更广泛适用， visit the help center 。

已关闭 11 年前。

// msort.h
#ifndef _MSORT_H

void msort(int a[], int b[], int left, int right);

#endif //_MSORT_H


// msort.c
#include "msort.h"

void msort(int a[], int b[], int left, int right)
{
    if (left < right)
    {
        msort(a, b, left, (left + right) / 2);
        msort(a, b, (left + right) / 2 + 1, right);
        merge(a, b, left, right);
    }
}


// merge.h
#ifndef _MERGE_H_

void merge(int a[], int b[], int low, int high);

#endif //_MERGE_H_ 




// merge.c
#include <stdio.h>
#include "merge.h"

void merge(int a[], int b[], int low, int high)
{
    int mid, begin1, end1, begin2, end2, k;

    mid = (low + high) / 2;
    begin1 = low;
    end1 = mid;
    begin2 = mid + 1;
    end2 = high;
    k = 0;

    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] <= a[begin2])
            b[k++] = a[begin1++];
        else
            b[k++] = a[begin2++];
    }

    while (begin1 <= end1)
        b[k++] = a[begin1++];

    while (begin2 <= end2)
        b[k++] = a[begin2++];
}





// test_merge.c
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <malloc.h>
#include "msort.h"
#include "merge.h"

#define N 10

int main()
{
    int *a, *b, i, left, right;

    left = 0;
    right = N - 1;

    a = malloc(sizeof(int) * N);
    if (a == NULL)
        exit(0);
    b = malloc(sizeof(int) * N);
    if (b == NULL)
        exit(0);

    srand((unsigned)time(NULL));

    printf("array before sort:\n");
    for (i = 0; i < N; i++)
    {
        a[i] = rand() % 50;
        printf("%-5d", a[i]);
    }
    printf("\n");

    msort(a, b, left, right);

    printf("array after sort:\n");
    for (i = 0; i < N; i++)
    {
        printf("%-5d", b[i]);
    }
    printf("\n");

    free(a);
    free(b);
    return 0;

}

以上是合并排序代码。 msort.h 和 msort.c 递归直到 数组顺序正确。 merge.h 和 merge.c 合并两个子数组。 test_merge.c 只是合并排序的测试。没有错误和警告时 编译并链接。但输出不按顺序，我找不到原因。

有人可以帮忙吗？

Answer 1

您永远不会修改 msort 或 merge 中的第一个数组，因此最终调用 msort 中的 merge code> 愉快地覆盖了对 msort 的递归调用中所做的事情，因此调用

msort(a, b, left, right);

在main中相当于

merge(a, b, left, right);

在merge中，您需要将合并后的 block 复制回数组a中，然后排序后的数组将位于a中>(也在 b 中)。

void merge(int a[], int b[], int low, int high)
{
    int mid, begin1, end1, begin2, end2, k;

    mid = (low + high) / 2;
    begin1 = low;
    end1 = mid;
    begin2 = mid + 1;
    end2 = high;
    k = 0;

    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] <= a[begin2])
            b[k++] = a[begin1++];
        else
            b[k++] = a[begin2++];
    }

    while (begin1 <= end1)
        b[k++] = a[begin1++];

    while (begin2 <= end2)
        b[k++] = a[begin2++];
    /* Now copy back into a */
    for(begin1 = low, begin2 = 0; begin1 <= high; ++begin1, ++begin2) {
        a[begin1] = b[begin2];
    } 
}