请找出此合并排序代码中的错误

Question

我已经提供了使用归并排序算法对数组进行排序的代码，但我找不到错误，该代码在输出时未给出正确排序的数组。递归调用函数mergesort对数组进行分割，直到其大小减为1。然后使用merge函数合并多个数组。

#include <bits/stdc++.h>

using namespace std;

void merge(int a[], int m, int l, int h) {
    int n1 = m - l + 1, n2 = h - m;
    int t1[n1], t2[n2];
    for (int i = 0; i < n1; i++) {
        t1[i] = a[i + l];
    }
    for (int i = 0; i < n2; i++) {
        t2[i] = a[i + m + 1];
    }
    int k = 0, p = 0, r = 0;
    while (k < n1 && p < n2) {
        if (t1[k] <= t2[p]) {
            a[r] = t1[k];
            k++;
            r++;
        } else {
            a[r] = t2[p];
            p++;
            r++;
        }
    }
    while (k < n1) {
        a[r] = t1[k];
        k++;
        r++;
    }
    while (p < n2) {
        a[r] = t2[p];
        p++;
        r++;
    }
}

void mergesort(int a[], int l, int h) {
    if (l < h) {
        int m = l + (h - l) / 2;
        mergesort(a, l, m);
        mergesort(a, m + 1, h);
        merge(a, m, l, h);
    }
}

int main() {
    int a[5] = { 1, 2, 3, 4, 5 };
    mergesort(a, 0, 4);
    for (int i = 0; i < 5; i++) {
        cout << a[i] << " ";
    }
    return 0;
}

Answer 1

merge 函数中的错误是 r 应该初始化为 l，而不是 0。您没有将切片合并到原始位置。

另请注意，此函数中的最后一个循环 while (p < n2) 是多余的：右侧切片中的剩余元素已经位于原始数组中的正确位置。

这是修改后的版本：

void merge(int a[], int m, int l, int h) {
    int n1 = m - l + 1, n2 = h - m;
    int t1[n1], t2[n2];
    for (int i = 0; i < n1; i++) {
        t1[i] = a[i + l];
    }
    for (int i = 0; i < n2; i++) {
        t2[i] = a[i + m + 1];
    }
    int k = 0, p = 0, r = l;
    while (k < n1 && p < n2) {
        if (t1[k] <= t2[p]) {
            a[r] = t1[k];
            k++;
            r++;
        } else {
            a[r] = t2[p];
            p++;
            r++;
        }
    }
    while (k < n1) {
        a[r] = t1[k];
        k++;
        r++;
    }
}

为了进一步简化代码，这里再做一些说明：

使用 h 作为切片末尾后的第一个索引的约定不会造成混淆。这样，初始调用使用数组长度，mergesort 可以将切片长度计算为 h - l。
变量名 l 看起来与数字 1.
merge的参数通常是l、m、h的顺序，m是开始的索引右切片。
右边的切片不需要保存。
使用具有自动存储功能的可变长度数组 t1[n2] 可能会导致大型数组 堆栈溢出 。

这是修改后的版本：

#include <bits/stdc++.h>

using namespace std;

void merge(int a[], int lo, int m, int hi) {
    int i, j, k;
    int n1 = m - lo;
    int t1[n1];
    for (i = 0; i < n1; i++) {
        t1[i] = a[lo + i];
    }
    i = 0;
    j = m;
    k = lo;
    while (i < n1 && j < hi) {
        if (t1[i] <= a[j]) {
            a[k++] = t1[i++];
        } else {
            a[k++] = a[j++];
        }
    }
    while (i < n1) {
        a[k++] = t1[i++];
    }
}

void mergesort(int a[], int lo, int hi) {
    if (hi - lo >= 2) {
        int m = lo + (hi - lo) / 2;
        mergesort(a, lo, m);
        mergesort(a, m, hi);
        merge(a, lo, m, hi);
    }
}

int main() {
    int a[5] = { 1, 5, 2, 4, 3 };
    mergesort(a, 0, 5);
    for (int i = 0; i < 5; i++) {
        cout << a[i] << " ";
    }
    cout << "\n";
    return 0;
}

请找出此合并排序代码中的错误

Please spot the error in this merge sort code

sorting

mergesort