C ++合并排序不工作并且崩溃

Question

我试图通过以下方式在 C++ 中实现归并排序：

#include <iostream>
using std::cout;
using std::endl;
using std::string;
using std::memcpy;

void mergeSort(int *array, int *temp, int leftStart, int rightEnd);
void mergeHalves(int *array, int *temp, int leftStart, int rightEnd);

void printArray(int* array, int size,string message){
    cout<<message<<endl;
    for (int i = 0; i < size; i++)
        cout << *(array+i) << "\t";
    cout << endl;
}
int main(){
    const int size = 10;
    int myInts[size] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    int temp[size] = {0};
    printArray(myInts,size,"Input");
    mergeSort(myInts, temp, 0, size-1);
    printArray(myInts, size, "Output:");

    return 0;
}

void mergeSort(int *array, int *temp, int leftStart, int rightEnd){
    if (leftStart >= rightEnd)
        return;

    int middle = (leftStart + rightEnd) / 2;

    mergeSort(array, temp, leftStart, middle);
    mergeSort(array, temp, middle + 1, rightEnd);
    mergeHalves(array,temp,leftStart,rightEnd);
    return;
}

void mergeHalves(int *array, int *temp, int leftStart, int rightEnd){
    int leftEnd = (rightEnd + leftStart) / 2;
    int rightStart = leftEnd + 1;
    int size = rightEnd - leftStart + 1;

    int left = leftStart;
    int right = rightStart;
    int index = leftStart;

    while (left <= leftEnd && right <= rightEnd){
        if (*(array+left) <= *(array+right)){
            *(temp+index) = *(array+left);
            left++;
        }else{
            *(temp+index) = *(array+right);
            right++;
        }
        index++;
    }

    memcpy(temp + index, array + left, (leftEnd - left + 1) * sizeof(int));
    memcpy(temp + index, array + right, (rightEnd - right + 1) * sizeof(int));
    memcpy(array, temp, size * sizeof(int));
}

我检查代码的次数越来越多，但我无法理解我遗漏了什么。
该算法在

的初始值下无法正常工作

myInts[size] = {3, 6, 4, 2, 7, 8, 9, 1, 0, 5}

因为它只对数组的前半部分进行了排序。
然后我尝试用代码中显示的输入更改输入，我得到以下输出：

Input
9   8   7   6   5   4   3   2   1   0   
Output:
3   2   1   0   -161742639  6   5   4   7   8   
Abort trap: 6

过了一会儿，我重新编译了运行相同的代码并得到了这个输出：

Input
9   8   7   6   5   4   3   2   1   0   
Output:
3   2   1   0   6   5   4   7   8   9

在我看来，某些赋值操作或复制操作出错了，而且在运行dom 上也出错了，但对我来说一切似乎都是正确的..

我试过逐步调试，程序的流程似乎没问题。

我在 MacOS X Sierra 10.12.6 上运行，我正在使用 g++ 进行编译。

我错过了什么？我快疯了..提前致谢！

编辑：我似乎已经解决了 Abort Trap 问题，我编辑了在 main 函数中传递 size-1 而不是 size 的代码.虽然仍然无法订购

Answer 1

经过大量调试，我发现了您的问题。您通过不同的函数将多个变量命名为同一事物。其中一些变量表示完全相同的事物 (leftStart、rightEnd)，而其他变量，如 size 表示两个完全不同的事物。

在 mergHalves 的末尾，您执行 memcpy(array, temp, size * sizeof(int)); 可能是因为您认为 size 是整个数组的大小，因此您要将所有内容复制回来。但是，不是。

该行应为 memcpy(array+leftStart, temp+leftStart, size * sizeof(int));，因为在此函数中您已将大小声明为 int size = rightEnd - leftStart + 1;。这是一个很好的例子，说明了为什么让你的变量名更长一点和更具描述性可以节省你几个小时的调试时间（并且必须 post 在 Whosebug 上）。

查看 ideone 上的实际修复。

最后，顺便说一句，我知道您想尝试 "the hard way," 不使用向量，但是请永远不要做 *(temp+index) 这样的事情。 subscript operator 正是为了这个目的而制作的，意味着 完全相同的东西 ，只是更具可读性。（即，改为 temp[index]）。

C ++合并排序不工作并且崩溃

c++ merge sort not working and crashing

c++

mergesort