c++ - 合并排序不能正确处理某些数字列表

Question

它可以正确处理第二个数字列表，但不能正确处理第一个数字列表，这是为什么？我该怎么做才能纠正它？我可以做的最小改变是什么来解决这个问题？我已经了解了这一点，现在我意识到它并不完全正确......

#include <iostream>
using namespace std;

void merge(int arr[], int start, int len) {
    int size = (len - start) + 1;
    int* b = new int[size]();
    int i = start;
    int mid = (start + len) / 2;
    int k = 0;
    int j = mid + 1;

    while (k < size) {
        if ((i <= mid) && (arr[i] < arr[j])) {
            b[k++] = arr[i++];
        }
        else {
            b[k++] = arr[j++];
        }
    }

    for (k = 0; k < size; k++) {
        arr[start + k] = b[k];
    }

    delete[] b;
}

void mergeSort(int data[], int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        mergeSort(data, start, mid);
        mergeSort(data, mid + 1, end);
        merge(data, start, end);
    }
}

void printArray(int arr[], int size) {
    cout << "--------------------------------------------------------" << endl;
    cout << "Printing ordered array of integers after merge sort" << endl;
    for (int i = 0; i < size; i++) {
        cout << arr[i] << endl;
    }
}

int main() {
    int data[10] = { 2, 4, 3, 1, 7, 9, 8, 6, 5, 10 };
    mergeSort(data, 0, 9);
    printArray(data, 10);

    //Merge Sort and Merge
    cout << "Calling Merge and Merge Sort Recursive Functions\n"
        "with array of 10 integers" << endl;
    int arrayOfInts[10] = { 10, 23, 34, 2, 56, 42, 78, 4, 84, 99 };
    mergeSort(arrayOfInts, 0, 9);

    printArray(arrayOfInts, 10);
    system("pause");
}

第一个数组生成 1,2,3,1,5,6,5,7,8,10，第二个数组生成一个排序数组。

Answer 1

错误在这里:

if ((i <= mid) && (arr[i] < arr[j]))

你需要确保i是<=比mid 和j是<=比len 。如果i或 j超出范围则进行比较是未定义的行为，而且进行比较也没有用。

一旦您得到一个超出范围的值，您就可以从另一侧复制值。

// Copy and compare while both i and j are in range.
while (i <= mid && j <= len) {
    if (arr[i] < arr[j]) {
        b[k++] = arr[i++];
    }
    else {
        b[k++] = arr[j++];
    }
}
// Copy remaining from fist range (could be zero)
while(i <= mid) {
    b[k++] = arr[i++];
}
// Copy remaining from second range (could be zero)
while(j <= len) {
    b[k++] = arr[j++];
}

现在代码已修复。您需要解决几个最佳实践问题。但是为此你应该把代码带到Code Review