C中的递归mergesort不修改原始数组

Question

我正在C中实现合并排序。我有一个合并函数-merge(int array[],int start,int middle,int end)和一个mergeSort函数-mergeSort(int*array,unsigned int size)。

如果对原始数组的前半部分和后半部分进行排序（例如:5,6,7,8,1,2,3,4),则合并排序可以很好地工作。这是因为我的merge函数无论在什么情况下都要传递原始数组，并且当它被赋予2个排序数组时（正如预期的那样），它可以工作。我的问题是他们什么时候不是。每次调用merge时，我的原始数组都没有被修改，尽管我已经对它进行了编程。有人能知道我的问题在哪里吗？代码在下面。

当我在输入{10,9,8,7,6,5,4,3,2,1}上运行此代码时，它将返回{5,4,3,2,1,0,10,9,8,7,6}。

void merge(int arr[], int l, int m, int r) {

    int size1 = m - l + 1;
    int size2 = r - m;

    int arr1[size1];
    int arr2[size2];

    int i;

    for ( i = 0; i < size1; i++ ) {
        arr1[i] = arr[l + i];
    }

    for ( i = 0; i < size2; i++ ) {
        arr2[i] = arr[m + i + 1];
    }

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

    while ( i < size1 && j < size2 ) {
        if ( arr1[i] < arr2[j] ) {
            arr[k] = arr1[i];
            i++;
            k++;
        } else {
            arr[k] = arr2[j];
            j++;
            k++;
        }
    }
    while ( i < size1 ) {
        arr[k] = arr1[i];
        i++;
        k++;
    }
    while ( j < size2 ) {
        arr[k] = arr2[j];
        j++;
        k++;
    }
}

void mergeSort(int *array, unsigned int size) {
    int start = 0;
    int middle = (size / 2) - 1;
    int end = size - 1;

    if ( size < 2 ) {
        return;
    }

    int m = ( size / 2 );

    int arr1[m];
    int arr2[size - m];

    int i;

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

    for ( i = middle + 1; i < size; i++ ) {
        arr2[i - (middle + 1)] = array[i];
    }

    mergeSort(arr1, m);
    mergeSort(arr2, size - m);
    merge(array, start, middle, end);
}

Answer 1

您的代码中存在多个问题：

• mergeSort函数将数组拆分为2个局部数组，并递归调用自身对它们进行排序，但merge阶段不将这些排序的数组作为输入。您应该直接使用参数数组的部分内容。
• 大小计算非常繁琐，许多调整会对size的小值造成问题。使用一个简单的约定：传递end作为第一个元素经过数组结尾的偏移量。这样计算大小只需从end减去start。
• merge函数将k初始化为0而不是l。

以下是一个修正版本：

void merge(int arr[], int start, int m, int end) {
    int size1 = m - start;
    int size2 = end - m;
    int arr1[size1];
    int arr2[size2];
    int i, j, k;

    for (i = 0; i < size1; i++) {
        arr1[i] = arr[start + i];
    }
    for (i = 0; i < size2; i++) {
        arr2[i] = arr[m + i];
    }

    i = j = 0;
    k = start;

    while (i < size1 && j < size2) {
        if (arr1[i] < arr2[j]) {
            arr[k++] = arr1[i++];
        } else {
            arr[k++] = arr2[j++];
        }
    }
    while (i < size1) {
        arr[k++] = arr1[i++];
    }
    while (j < size2) {
        arr[k++] = arr2[j++];
    }
}

void mergeSort(int *array, unsigned int size) {
    if (size >= 2) {
        int m = size / 2;
        mergeSort(array, m);
        mergeSort(array + m, size - m);
        merge(array, 0, m, size);
}

Bob__建议进行简化，只将数组的前半部分保存到ARR1中，而不需要ARR2。这里是一个修改版本，还删除了start（始终为0）和其他一些简化：

void merge(int arr[], size_t m, size_t size) {
    int arr1[m];
    size_t i, j, k;

    for (i = j = k = 0; j < m; j++) {
        arr1[j] = arr[j];
    }

    while (i < m && j < size) {
        if (arr1[i] < arr[j]) {
            arr[k++] = arr1[i++];
        } else {
            arr[k++] = arr[j++];
        }
    }
    while (i < m) {
        arr[k++] = arr1[i++];
    }
}

void mergeSort(int *array, size_t size) {
    if (size >= 2) {
        size_t m = size / 2;
        mergeSort(array, m);
        mergeSort(array + m, size - m);
        merge(array, m, size);
}

但是请注意，为arr1分配自动存储（也就是堆栈上的存储）可能会导致大型数组（通常大于几十万个元素）的未定义行为。从堆中分配临时数组可以避免这个问题，但代价是额外的开销和分配失败的可能性。

Answer 2

在mergeSort中，在执行mergeSort(arr1,m)和mergeSort(arr2,size-M)之后，实际上并没有对arr1和arr2执行任何操作。

对于一个简单的修复，我建议不要使用变量ARR1和ARR2，而是直接对array的部分调用mergeSort，如下所示：

void mergeSort(int* array, unsigned int size) {
    int start = 0;
    int middle = (size / 2);
    int end = size - 1;

    if ( size < 2 ) {
        return;
    }

    mergeSort(array, middle);
    mergeSort(array + middle, size - middle);
    merge(array, start, middle - 1, end);
}