c++ - 递归合并排序函数给出错误的输出

Question

我想弄清楚为什么我的合并排序功能不起作用。我相信问题出在它的 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++;
        }
    } 

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

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

传入数组 {4, 13, 8, 12, 9 } 会返回 {4, 8, 8, 9, 9}

我的另一个想法是 i 和 j 变量没有正确递增。我反复检查这段代码，似乎找不到解决方案。

Answer 1

这(merge 函数的第一行)

int *temp = data;

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

你可能需要做这样的事情:

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，这样它就可以用作临时内存(即临时内存)进行合并。或者，如果您真的很聪明，可以在实际内存和暂存内存之间乒乓，以尽量减少复制。