c++ - 为什么我的合并排序不起作用？

Question

它编译得很好，但是当它运行时，它会向列表中添加随机高位数字，以及现有数字的拷贝。我已经让几个人检查过这个，但没有人能弄明白。

void mergeSort(int list[], int length) {
    recMergeSort(list, 0, length - 1);
}

void recMergeSort(int list[], int first, int last) {

    if (first < last) {
        int mid = (first + last) / 2;
        recMergeSort(list, first, mid);
        recMergeSort(list, mid + 1, last);
        merge(list, first, last, mid);
    }
}

void merge(int list[], int first, int last, int mid) {

    int arraySize = last - first + 1;
    int* tempList = new int[arraySize];
    int beginPart1 = first;
    int endPart1 = mid;
    int beginPart2 = mid + 1;
    int endPart2 = last;


    int index = beginPart1;


    while (beginPart1 <= endPart1 && beginPart2 <= endPart2) {
        if (list[beginPart1] < list[beginPart2]) {
            tempList[index] = list[beginPart1];
            beginPart1++;
        }
        else {
            tempList[index] = list[beginPart2];
            beginPart2++;
        }
        index++;
    }

    while (beginPart1 <= endPart1) {
        tempList[index] = list[beginPart1];
        index++;
        beginPart1++;
    }

    while (beginPart2 <= endPart2) {
        tempList[index] = list[beginPart2];
        index++;
        beginPart2++;
    }


    for (int i = first; i <= last; i++) {
        list[i] = tempList[i - first];
    }

    delete[] tempList;
}

Answer 1

在函数 merge() 中，您错误地计算了 index 变量:

假设 begin = 10，mid = 14，end = 19(总数组大小为 0 .. 19，并且您正在 recMergeSort() 上半部分)，您的索引 = 10，但是 tempList 数组的索引为 0..9(因为 arraySize = last - first + 1 = = 10).

所以你溢出了你的 tempList 数组，当你“合并”时，你会得到数据损坏。

将您的 index 变量固定为从 0 开始(而不是从 beginPart1 开始)。