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()ing 上半部分)，您的索引 = 10，但 tempList 数组的索引为 0..9(因为 arraySize = last - first + 1 = = 10)。

因此，您的 tempList 数组溢出，当您“合并”时，数据会损坏。

将您的 index 变量修复为从 0 开始(而不是基于 beginPart1)。