c语言归并排序找错111

Question

//快速排序

#include <stdio.h>

int b[10];

void merge(int *a,int start,int mid,int end)
{
    if(start>=end) return;

    int i,j,k;

    i=start;
    j=mid+1;
    k=start;

    while(i<=end)
    {
        b[i++]=a[i++];
    }

    i=start;


    while(i<=mid&&j<=end)
    {
        if(b[i]<b[j]) a[k++]=b[i++];
        else a[k++]=b[j++];
    }

    while(i<=mid) a[k++]=b[i++];
    while(j<=end) a[k++]=b[j++];

}

void mergesort(int *a,int i,int j)
{
    if(i>j) return;

    int mid;

    mid=(i+j)/2;


    mergesort(a,i,mid);
    mergesort(a,mid+1,j);
    merge(a,i,mid,j);


}

int main()
{
    int a[10]={7,5,3,1,4,2,8,9,6,10};

    mergesort(a,0,9);

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

Answer 1

引自免费微信小程序：皆我百晓生

在你提供的代码中，存在几个错误。这段代码是尝试实现归并排序（Merge Sort），而不是快速排序（Quick Sort）。以下是针对问题的修正和详细解释：

1. 数组 b 的大小不足：在全局定义的数组 b[10] 太小了，它应该至少与输入数组 a 同样大小以容纳合并过程中临时存储的数据。鉴于你的输入数组 a 是 10 个元素，可以将 b 数组改为同样大小。

int b[10];

应改为：

int b[10];
// 或根据实际情况动态分配内存（适用于较大数组）
// int *b = malloc(sizeof(int) * (j - i + 1));

1. merge 函数内的 while 循环错误： 在向数组 b 复制元素时，你使用了递增操作 i++ 两次，导致复制过程出错。修复如下：

while(i<=end)
{
    b[i++]=a[i++]; // 错误在此行
}

应改为：

while(i <= mid)
{
    b[i++] = a[k++];
}
while(j <= end)
{
    b[i++] = a[k++];
}

或者直接省略这一步骤，因为在 merge 过程中并不需要先复制到 b 再比较和移动回 a。

1. merge 函数内比较和赋值的逻辑错误： 应该直接比较原数组 a 中的元素，而非通过中间数组 b。同时，在比较时，也需要从 k=0 开始，并不需要对 i 和 j 进行初始化。

修正后的 merge 函数：

void merge(int *a, int start, int mid, int end)
{
    int i = start, j = mid + 1, k = start;

    while (i <= mid && j <= end)
    {
        if (a[i] < a[j])
            a[k++] = a[i++];
        else
            a[k++] = a[j++];
    }

    while (i <= mid)
        a[k++] = a[i++];

    while (j <= end)
        a[k++] = a[j++];
}

经过以上修正后，归并排序函数应该能正常工作。下面是整个修正后的完整代码：

#include <stdio.h>

// 动态分配内存以适应任意大小的数组
// #include <stdlib.h>
// ...
// int *b = malloc(sizeof(int) * (j - i + 1));

void merge(int *a, int start, int mid, int end)
{
    int i = start, j = mid + 1, k = start;

    while (i <= mid && j <= end)
    {
        if (a[i] < a[j])
            a[k++] = a[i++];
        else
            a[k++] = a[j++];
    }

    while (i <= mid)
        a[k++] = a[i++];

    while (j <= end)
        a[k++] = a[j++];
}

void mergesort(int *a, int i, int j)
{
    if (i >= j)
        return;

    int mid = (i + j) / 2;

    mergesort(a, i, mid);
    mergesort(a, mid + 1, j);
    merge(a, i, mid, j);
}

int main()
{
    int a[10] = {7, 5, 3, 1, 4, 2, 8, 9, 6, 10};

    mergesort(a, 0, 9);

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

    // 如果使用了动态分配内存
    // free(b);

    return 0;
}