在 C 中的数组中合并排序算法 - .exe 不是运行？

Question

以下是我的 'C' MergeSort 算法代码。我正在使用 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;
}

我的代码根本没有运行，并立即显示错误 window。

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

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

#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;
}

--- 最新编辑 ---

新代码在 Merge 中进行了修改，其工作方式如下：

#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 的 return 值存储在 A[n] 中？ A[n] 不仅越界，而且赋值没有任何意义，而且参数 A[n] 也是伪造的。 MergeSort 的 return 类型无论如何应该是 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 数组是分开的，你不应该用 mid 偏移 right 中的索引。在比较最左边的剩余元素之前，您还应该测试 left 或 right 两半是否已用完。您目前遇到未定义的行为。

Answer 2

int n = sizeof(A);

这将使 n 成为 40 ，因此 A[n] 超出范围。

函数中int MergeSort

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

所以这里数组 right 索引以 index=mid 开头（数组索引以 0 开头）。

并且在函数中int Merge

    int n = nL + nR;
int i, j, k = 0;    //i and j not initialized .
int A[n];

for ( k = 0; k < n; k++ )
{
    if( left[i] <= right[mid + j] )  // Used here. What i and j have ?
    {
        A[k] = left[i];
        i = i + 1;
    }
    else
    {
        A[k] = right[mid + j];
        j = j + 1;
    }

在这个函数中 i j 没有被初始化并用作数组 index.Thus 又是一个出错的原因。

在 C 中的数组中合并排序算法 - .exe 不是运行？

Merge sort algorithm in an array in C - .exe not running?

c

sorting

runtime-error

mergesort

在 C 中的数组中合并排序算法 - .exe 不是 运行？

Merge sort algorithm in an array in C - .exe not running?

c

sorting

runtime-error

mergesort

在 C 中的数组中合并排序算法 - .exe 不是运行？