C中没有第二次递归调用的MergeSort

Question

我要删除 MergeSort 的第二个调用递归，(MergeSort(tabla, m + 1, iu);)

我真的很努力，但无论我做什么，它总是对 table 进行部分排序，但它永远不会完全排序。

int MergeSort(int* tabla, int ip, int iu) {
    int m, A;
    if (ip > iu)return ERR;
    if (ip == iu)return 0;

    m = (ip + iu) / 2;

    A = MergeSort(tabla, ip, m);
    A += MergeSort(tabla, m + 1, iu);
    return Merge(tabla, ip, iu, m) + A;
}

P.S: Merge 合并 table.

int Merge(int * tabla, int ip, int iu, int imedio) {
    int i = ip, j = imedio + 1, k = 0, OB = 0;
    int *taux = (int*) calloc(iu - ip + 1, sizeof (int));
    if (!taux)return ERR;

    while (i <= imedio && j <= iu) {
        OB++;
        if (tabla[i] < tabla[j]) {
            taux[k] = tabla[i];
            i++;
        } else {
            taux[k] = tabla[j];
            j++;
        }
        k++;
    }

    if (i > imedio) { /* copy the right table */
        while (j <= iu) {
            taux[k] = tabla[j];
            j++;
            k++;
        }
    } else if (j > iu) { /* copy the left table */
        while (i <= imedio) {
            taux[k] = tabla[i];
            i++;
            k++;
        }
    }

    for (i = ip; i <= iu; i++) /* Copy function */
        tabla[i] = taux[i - ip];

    free(taux);

    return OB;
}

[编辑]：添加合并代码。

Answer 1

您无法删除尾递归，因为您的算法中没有尾递归。即使是对 Merge 的最终调用也无法转换为尾调用，因为您将其结果添加到本地值。相反，编译可能会内联 Merge 函数的代码，如果它是 static 并且定义在 MergeSort 函数之前，或者您可以将初始计数作为参数传递

可能你拆分数组的方式有问题：m是中点，左半部分应该从ip包含到m不包含，而右半部分将从 m 包含到 iu 排除。这将与顶层的调用一致：

n = MergeSort(array, 0, count);

在您的代码中，您处理包含的上边界并将 m+1 作为右半部分的起始索引传递，但这会导致更复杂的代码和顶层的反直觉调用。

您还需要在递归期间的每个点测试分配错误。

这里是Merge的简化版本：

static int Merge(int *tabla, int ip, int iu, int imedio, int count) {
    int i = ip, j = imedio, k = 0;
    int *taux = malloc((iu - ip) * sizeof(*taux));
    if (!taux) return ERR;

    while (i < imedio && j < iu) {
        count++;
        if (tabla[i] < tabla[j]) {
            taux[k++] = tabla[i++];
        } else {
            taux[k++] = tabla[j++];
        }
    }
    while (i < imedio) { /* copy the remaining elements from left table */
        taux[k++] = tabla[i++];
    }
    while (j < iu) { /* copy the remaining elements from right table */
        taux[k++] = tabla[j++];
    }
    for (i = ip; i < iu; i++) { /* copy back to source */
        tabla[i] = taux[i - ip];
    }
    free(taux);

    return count;
}

如果您真的想要删除对MergeSort的第二次调用，您可以使用循环：

int MergeSort(int* tabla, int ip, int iu) {
    int m, count = 0, n, a, b;

    if (ip > iu) return ERR;

    m = (ip + iu) / 2;
    if (m == ip)
        return 0;

    for (a = ip, b = m; a < iu; a = b, b = iu) {
        n = MergeSort(tabla, a, b);
        if (n == ERR) return ERR;
        count += n;
    }
    return Merge(tabla, ip, iu, m, count);
}

请注意，您可以通过这些想法提高效率：

可以在顶层分配一个辅助数组并将其作为参数传递给 MergeSortAux 内部函数，从而大大提高效率。
不需要复制右边的剩余元素。
辅助数组不需要和源数组一样大。
如果数组已经按升序或降序排序，还有一些额外的技巧可以减少比较次数。

C中没有第二次递归调用的MergeSort

MergeSort without second recursion call in C

c

recursion

mergesort