0 
// 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 只是合并排序的测试。编译和链接时没有错误和警告。但是输出不正常，我找不到原因。

任何人都可以提供一些帮助吗？

4

1 回答 1

2

您永远不会修改msortor中的第一个数组，因此对inmerge的最终调用会愉快地覆盖递归调用中所做的事情，因此调用mergemsortmsort

msort(a, b, left, right);

inmain相当于

merge(a, b, left, right);

在merge中，您需要将合并的块复制回数组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];
    } 
}
于 2012-05-25T15:00:29.663 回答