MergeSort递归

Question

// main function 
void mergeSort(int input[],int size){ // 
    if(size == 0 || size == 1) return;  //base case
    int m = size/2; //finding the mid 
    mergeSort(helper(input,0,m),m);  //left array
    mergeSort(helper(input,m,size),size-m);  // right array
    merge(input,0,m,size); // merging the both arrays
}

void merge(int *input,int start,int size1,int size) //merging array in increasing order
{
    int a[size];
    int i=start,j=size1,k=0;
    while(i < size1 && j < size){
        if(input[i] < input[j]){
            a[k++] = input[i++];
        }
        else{
            a[k++] = input[j++];
        }
    }
    while(i < size1){
        a[k++] = input[i++];
    }
    while(j < size){
        a[k++] = input[j++];
    }
    for(int i=0;i<size;i++){
        input[i] = a[i];
    }
}
int* helper(int input[],int s,int e){// this function helps get the half array
    int a[e-s];
    for(int i=s,j=0;i<e;i++,j++){
        a[j] = input[i];
    }
    for(int i=0;i<e-s;i++){
        input[i] = a[i];
    }
    return input;
}

我无法调试这段代码，任何人都能告诉我为什么这不对，我在助手函数的帮助下将两者分开，然后将其传递给合并以获得输出。

Answer 1

这是一个完整的合并排序算法。

首先，定义一个函数将给定的数组拆分为两个子数组，然后将它们合并回排序。

void merge(int *array, int start, int mid, int end)
{
    // 1. Split array into two subarrays: left and right
    const int left_size = mid - start + 1;
    const int right_size = end - mid;

    int left_subarray[left_size];
    int right_subarray[right_size];

    int i;
    for (i = 0; i < left_size; i++)
        left_subarray[i] = array[start + i];

    int j;
    for (j = 0; j < right_size; j++)
        right_subarray[j] = array[mid + 1 + j];

    // 2. Merge them sorted into array
    i = 0; j = 0;
    int k;
    for (k = start; i < left_size && j < right_size; k++) {
        if (left_subarray[i] <= right_subarray[j])
            array[k] = left_subarray[i++];
        else
            array[k] = right_subarray[j++];
    
    }

    for (; i < left_size; i++)
        array[k++] = left_subarray[i];

    for (; j < right_size; j++)
        array[k++] = right_subarray[j];
}

merge()的第一部分解释了如何将数组拆分为两个子数组。现在可以使用递归对数组进行合并排序：

void merge_sort(int *array, int start, int end)
{
    if (start >= end)
        return;

    int mid = start + (end - start) / 2;

    merge_sort(array, start, mid);
    merge_sort(array, mid + 1, end);

    merge(array, start, mid, end);
}

您可以定义一个函数来帮助您打印数组：

void print_array(int *array, int size, const char *sep)
{
    int i;
    for (i = 0; i < size; i++)
        printf("%d%s", array[i], sep);

    printf("\n");
}

下面是一个示例程序：

int main()
{
    int array[] = {9, 6, 8, 7, 5, 4, 0, 3, 2, 1};
    const int size = sizeof(array) / sizeof(*array);

    printf("Unsorted array:\t");
    print_array(array, size, " ");
    
    merge_sort(array, 0, size-1);
    
    printf("Sorted array:\t");
    print_array(array, size, " ");
}