c - C 数组中的合并排序算法 - .exe 未运行？

Question

以下是我的合并排序算法的“C”代码。我正在使用 Dev C++，使用 TDM:GCC 编译器。没有给出编译错误，但编译后exe不运行。请帮忙。

#include<stdio.h>
#include<conio.h>

int main()
{
    int A[] = {12, 5, 6, 78, 223, 1, 45, 34, 78, 99};
    int n = sizeof(A);
    int i = 0;

    A[n] = MergeSort(A[n], n);

    for ( i = 0; i < n; i++ ) printf("%d\n", A[i]);

    return 0;
}

int MergeSort(int A[], int n)
{
    int mid = n/2;
    int left[mid], right[n - mid];
    int i;

    if(n<2) return;

    for ( i = 0; i < mid; i++ )
        left[i] = A[i];
    for ( i = mid; i < n; i++ )
        right[i] = A[i];

    int nL = sizeof(left);
    int nR = sizeof(right);

    MergeSort(left, nL);
    MergeSort(right, nR);
    Merge(left, right, nL, nR, mid);
}

int Merge(int left[], int right[], int nL, int nR, int mid)
{
    int n = nL + nR;
    int i, j, k = 0;
    int A[n];

    for ( k = 0; k < n; k++ )
    {
        if( left[i] <= right[mid + j] )
        {
            A[k] = left[i];
            i = i + 1;
        }
        else
        {
            A[k] = right[mid + j];
            j = j + 1;
        }

        if ( i + j >= n) break;
    }

    return;
}

我的代码根本不运行，并立即显示一个错误窗口。

------编辑------

我新编辑的代码如下。现在没有错误，但仍然没有进行排序。

#include<stdio.h>
#include<conio.h>

int Merge(int left[], int right[], int nL, int nR, int A[])
{
    int n = nL + nR;
    int i = 0;
    int j = 0;
    int k = 0;

    for ( k = 0; k < n; k++ )
    {
        if(i < nL && j < nR && left[i] <= right[j] )
        {
            A[k] = left[i];
            i = i + 1;
        }
        else
        {
            A[k] = right[j];
            j = j + 1;
        }
    }

    return;
}

void MergeSort(int A[], int n)
{
    int mid = n/2;
    int left[mid], right[n - mid];
    int i;

    if(n<=1) return;

    for ( i = 0; i < mid; i++ )
        left[i] = A[i];
    for ( i = 0; i < n - mid; i++ )
        right[i] = A[i + mid];

    int nL = sizeof(left)/sizeof(left[0]);
    int nR = sizeof(right)/sizeof(right[0]);

    MergeSort(left, nL);
    MergeSort(right, nR);
    Merge(left, right, nL, nR, A);
}

int main()
{
    int A[] = {98, 5, 6, 78, 223, 1, 45, 34, 78, 99};
    int n = sizeof(A)/sizeof(A[0]);
    int i = 0;

    MergeSort(A, n);

    for ( i = 0; i < n; i++ ) printf( "%d\n", A[i] );

    return 0;
}

--- 最新编辑 ---

经过合并修改的新代码的工作原理如下:

#include<stdio.h>
#include<conio.h>

int Merge(int left[], int right[], int nL, int nR, int A[])
{
    int n = nL + nR;
    int i = 0;
    int j = 0;
    int k = 0;

    for ( k = 0; k < n; k++ )
    {
        if(j >= nR || (i < nL && left[i] <= right[j]))
        {
            A[k] = left[i];
            i = i + 1;
        }
        else
        {
            A[k] = right[j];
            j = j + 1;
        }
    }

    return;
}

void MergeSort(int A[], int n)
{
    int mid = n/2;
    int left[mid], right[n - mid];
    int i;

    if(n<=1) return;

    for ( i = 0; i < mid; i++ )
        left[i] = A[i];
    for ( i = 0; i < n - mid; i++ )
        right[i] = A[i + mid];

    int nL = sizeof(left)/sizeof(left[0]);
    int nR = sizeof(right)/sizeof(right[0]);

    MergeSort(left, nL);
    MergeSort(right, nR);
    Merge(left, right, nL, nR, A);
}

int main()
{
    int A[] = {98, 5, 6, 78, 223, 1, 45, 34, 78, 99};
    int n = sizeof(A)/sizeof(A[0]);
    int i = 0;

    MergeSort(A, n);

    for ( i = 0; i < n; i++ ) printf( "%d\n", A[i] );

    return 0;
}

感谢chqrlie和其他人的努力! :)

Answer 1

您的代码有多个问题...

最重要的是，您可以使用 sizeof 来获取数组中的元素数量。这只适用于 char 类型和类似类型。对于任何较大的类型，您需要将字节大小除以元素的大小:

n = sizeof(A) / sizeof(A[0]);

MergeSort 函数中需要进行相同的修复，但在实例化数组之前计算左右半部分的大小的局部变量会更简单。

为什么将 MergeSort 的返回值存储在 A[n] 中？不仅 A[n] 越界，而且赋值没有任何作用，而且参数 A[n] 也是假的。无论如何，MergeSort 的返回类型应该是 void。此行应为:

MergeSort(A, n);

在函数MergeSort中，右半部分的初始化循环不正确:

for ( i = mid; i < n; i++ )
    right[i] = A[i];

应该是:

for ( i = mid; i < n; i++ )
    right[i - mid] = A[i];

合并阶段也不正确:您应该将 A 作为参数传递，而不是使其成为局部变量。 mid 不是一个有意义的参数，left 和 right 数组是分开的，您不应该偏移 right 中的索引>中。在比较最左边的剩余元素之前，您还应该测试左半部分或右半部分是否已耗尽。您当前遇到未定义的行为。