c++ 中的合并排序算法有什么问题

Question

我从 gfg 课程中学到了这一点，即使他们给出的代码 link 与我编写的代码相似，但仍然无法在其中找到问题：

#include <iostream>
#include <algorithm>

using namespace std;

void merge(int a[], int low, int mid, int high) {
    int m = mid - low + 1, n = high - mid;
    int left[m], right[n];
    for (int i = 0; i < m; i++) {
        left[i] = a[low + i];
    }
    for (int j = 0; j < n; j++) {
        right[j] = a[m + j];
    }
    int i = 0, j = 0, k = low;
    while (i < m && j < n) {
        if (left[i] <= right[j]) {
            a[k] = left[i];
            i++;
            k++;
        } else {
            a[k] = right[j];
            j++;
            k++;
        }
    }
    while (i < m) {
        a[k] = left[i];
        i++;
        k++;
    }
    while (j < n) {
        a[k] = right[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l >= r) {
        return;
    }
    if (r > l) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

int main() {
    int n;
    cout << "enter size of array: ";
    cin >> n;
    int arr[n];
    cout << "enter element in array: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    mergeSort(arr, 0, n - 1);
    cout << "array after sort: \n";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

这是将输入作为 {10,5,30,15,7} 它 returns 输出作为 {5,10,10,15,30}

的代码

Here is the output screen shot for reference

Answer 1

您混淆了 m 变量（左数组的大小）与 mid（左数组的最后一个索引）

而不是这个：

for(int j=0;j<n;j++){
    right[j] = a[m+j];
}

这个：

for (int j = 0; j < n; j++) {
    right[j] = a[mid + j + 1];
}

专业提示：一个字母变量可以作为 for 循环中的索引。但是对于其他任何东西，都要给这个名字一个明显的含义。例如，将它们命名为 leftArraySize 和 rightArraySize，而不是 m 和 n。将它们命名为 firstIndex 和 lastIndex，而不是 l 和 r。当您在名称有意义的地方使用钝变量名称时，错误在哪里会很明显。

Answer 2

代码中的错误在 right 的初始化循环中：a[m + j] 应该是 a[mid + j + 1]

但是请注意，复制数组的右半部分是不必要的，因为这些元素在最终被覆盖之前就被复制了。

merge函数可以简化为：

void merge(int a[], int low, int mid, int high) {
    int m = mid - low + 1;
    int left[m];
    for (int i = 0; i < m; i++) {
        left[i] = a[low + i];
    }
    int i = 0, j = mid + 1, k = low;
    while (i < m && j <= high) {
        if (left[i] <= a[j]) {
            a[k] = left[i];
            i++;
            k++;
        } else {
            a[k] = a[j];
            j++;
            k++;
        }
    }
    while (i < m) {
        a[k] = left[i];
        i++;
        k++;
    }
}

另请注意，所有这些 +1 / -1 调整都令人困惑且容易出错。您可以通过传递 high 作为要排序的切片之外的元素的索引和 mid 右半部分第一个元素的索引来简化代码。将变量命名为 l 也很容易出错，因为 l 看起来与 1.

非常相似，容易混淆。

这是代码的修改版本：

#include <iostream>
#include <algorithm>

using namespace std;

void merge(int a[], int low, int mid, int high) {
    int m = mid - low;
    int left[m];
    for (int i = 0; i < m; i++) {
        left[i] = a[low + i];
    }
    int i = 0, j = mid, k = low;
    while (i < m && j < high) {
        if (left[i] <= a[j]) {
            a[k++] = left[i++];
        } else {
            a[k++] = a[j++];
        }
    }
    while (i < m) {
        a[k++] = left[i++];
    }
}

void mergeSort(int arr[], int low, int high) {
    if (high - low >= 2) {
        int mid = low + (high - low) / 2;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid, high);
        merge(arr, low, mid, high);
    }
}

int main() {
    int n;
    cout << "enter size of array: ";
    cin >> n;
    int arr[n];
    cout << "enter element in array: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    mergeSort(arr, 0, n);
    cout << "array after sort: \n";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    return 0;
}

merge函数可以进一步简化为：

void merge(int a[], int low, int mid, int high) {
    int m = mid - low;
    int left[m];
    for (int i = 0; i < m; i++) {
        left[i] = a[low + i];
    }
    int i = 0, j = mid, k = low;
    while (i < m) {
        if (j >= high || left[i] <= a[j]) {
            a[k++] = left[i++];
        } else {
            a[k++] = a[j++];
        }
    }
}

c++ 中的合并排序算法有什么问题

What's the issue in this merge sort algorithm in c++

c++

sorting

algorithm

mergesort