c++ - 递归合并排序功能给出错误的输出

我试图弄清楚为什么我的合并排序功能不起作用。我相信问题出在它的merge()部分之内。这是我的代码:

int mergeSort(int *data, int left, int right) {
    //divide
    if (left < right) {
        int q = floor((left + right) / 2);
        //conquer
        mergeSort(data, left, q);
        mergeSort(data, q + 1, right);
        //combine
        merge(data, left, q, right);
    }

    //print results for testing purposes
    for (int i = 0; i < n; i++) {
        cout << data[i] << "\n";
    }

    return 0;
}

这是它的merge()部分。我相信问题在于这部分。

int merge(int *data, int left, int q, int right) {
    int *temp = data;
    int i = left, j = q + 1, z = left;
    int t1 = 0, t2 = 0;
    while (i <= q && j <= right) { //while both variables have not reached the end of their sub arrays
        if (temp[i] <= temp[j]) {
            data[z] = temp[i];
            i++;
        }
        else {
            data[z] = temp[j];
            j++;
        }
        z++;
    }
     //if subarrays are both sorted and in order, combine them
    if (i < q) {
        t1 = z, t2 = i;
        for (t1; t1 < right;) {
            data[t1] = temp[t2];
            t1++;
            t2++;
        }
    }

    else if (j < right) {
        int t1 = z; int t2 = j;
        for (t1; t1 <= right;) {
            data[t1] = temp[t2];
            t1++;
            t2++;
        }
    }

我认为我的问题出在int *temp = data;的开头声明了merge()。我的想法是，这两个数组之间出现某种内存地址冲突，但是我不确定。

我尝试以不同的顺序排列数据，并发现当需要将数据从索引n移到索引n-i时，这两个索引之间的每个索引都将替换为n的值。例如:

在数组{4, 13, 8, 12, 9 }中传递将返回{4, 8, 8, 9, 9}
我的另一个想法是i和j变量没有正确递增。我反复查看过此代码，似乎找不到解决方案。

最佳答案

这(merge函数的第一行)

int *temp = data;

NOT 是否复制数组；它只是创建另一个指向相同内存的指针。这将导致您的代码覆盖您的数据。

您可能需要执行以下操作:

int * temp = new int [right - left + 1];
memcpy (temp, data + left, (right - left + 1) * sizeof(int));

并且不要忘了在函数末尾对delete[]的内存进行temp编码:

delete[] temp;

注意，您需要更改对z的使用；它应该从0开始，而不是从left开始。

(以下是可选的性能改进；您可以忽略它们。)
在每个merge函数中分配和释放内存是一个坏主意。特别地，由于我们确切地知道合并所需的总内存量:一组精确的n整数。

因此，最好将另一个大小相同的数组与data一起传递给mergeSort，以便将其用作暂存器(即临时存储器)进行合并。或者，如果您真的很聪明，则可以在实际内存和暂存内存之间进行乒乓操作，以最大程度地减少复制。