c - 合并排序不适用于所有情况

Question

我为合并排序编写了以下代码:

#include <stdio.h>

void mergeSort(int array[],int left, int right);

void mergeArray(int array[],int left,int middle, int right);

void mergeArray(int array[],int left,int middle, int right)
{

    int n1 = middle - left + 1;
    int n2 = right - middle ;

    int temp_a[n1];
    int temp_b[n2];

    int i = 0;
    int j = 0;
    int k = 0;

    for ( i = left ; i <= middle ; i++ )
    {
        temp_a[k++] = array[i];
    }

    for ( i = middle + 1 ; i < right + 1; i++ )
    {
        temp_b[j++] = array[i];
    }

    // now merge these two arrays


     i = 0;
     j = 0;
     k = 0;


    while ( i < n1 && j < n2 )
    {
        if ( temp_a[i] < temp_b[j])
        {
            array[k++] = temp_a[i++];

        }
        else
        {
            array[k++] = temp_b[j++];
        }
    }

    while ( i < n1 )
    {
        array[k++] = temp_a[i++];       
    }

    while ( j < n2 )
    {
        array[k++] = temp_b[j++];
    }



}


void mergeSort(int array[],int left, int right)
{
    // since there is only one element in the array.
    printf("I am in merge sort. left : %d, right : %d\n",left,right);
    if ( right - left < 1 )
    {
        return;
    }
    else
    {
        int middle = ( right - left ) / 2 ;
        mergeSort( array,left, middle );    
        mergeSort( array, middle +1 , right);

        mergeArray(array,left,middle,right);
    }


}

int main(int argc, char const *argv[])
{
    int n = 3;
    int i;

    int array[] = { 12,11,14,19};

    mergeSort(array,0,n);
    printf("\nArray is: \n");

    for (i = 0; i <= n; ++i)
    {
        printf("%d\n",array[i] );
    }
    return 0;
}

上述代码适用于 n = 1 和 n = 2，但不适用于其他值。

Answer 1

三个问题:(1) 在 mergeArray 中，您使用 n1 代替 n2 来处理 temp_b。将其更改为:

int temp_b[n2];

(2) 创建temp_a和temp_b后，在注释“now merge这两个数组”之后，需要将k设置为左而不是0:

k = left;

(3) 在 mergeSort 中，您的 middle 表达式不正确，您需要添加而不是减去:

int middle = ( right + left ) / 2 ;

它应该适用于这三个更改。