基于CLRS的C++ Merge Sort实现异常：输出大量重复值求助

问题描述 #

尝试基于CLRS实现C++版归并排序，运行后输出结果出现大量重复值，无法定位问题，认为merge函数逻辑无误。

原代码 #

#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& nums, int p, int q, int r);
void mergeSort(vector<int>& nums, int p, int r){
    if (p < r) {
        int q = (p + r) / 2;
        mergeSort(nums, p, q);
        mergeSort(nums, q + 1, r);
        merge(nums, p, q, r);
    }
}
void merge(vector<int>& nums, int p, int q, int r) {
    int s1 = p, s2 = q + 1;
    vector<int> l1, l2;
    for (int i = s1; i <= q; i++) {
        l1.push_back(nums[i]);
    }
    for (int i = s2; i <= r; i++) {
        l2.push_back(nums[i]);
    }
    int left = 0, right = 0;
    int idx = 0;
    while (left < l1.size() && right < l2.size()) {
        if (l1[left] < l2[right]) {
            nums[idx] = l1[left++];
        }
        else {
            nums[idx] = l2[right++];
        }
        idx++;
    }
    while (left < l1.size()) {
        nums[idx++] = l1[left++];
    }
    while (right < l2.size()) {
        nums[idx++] = l2[right++];
    }
}

int main() {
    vector<int> vect;
    vect.push_back(1);
    vect.push_back(3);
    vect.push_back(12);
    vect.push_back(23);
    vect.push_back(4);
    vect.push_back(11);
    vect.push_back(44);
    vect.push_back(322);
    mergeSort(vect, 0, vect.size() - 1);
    for (int i = 0; i < vect.size(); i++) {
        cout << vect[i] << endl;
    }
    return 0;
}

问题定位 #

核心错误出在merge函数的idx变量初始化：

• 你将idx设为0，但每次merge操作的目标是覆盖nums数组中从p到r的子区间，而非从数组头部开始。
• 错误地从索引0开始赋值会覆盖前面已经排序完成的元素，导致最终结果出现大量重复值。

修复后的代码 #

只需要修改merge函数中idx的初始值为p即可：

#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& nums, int p, int q, int r);
void mergeSort(vector<int>& nums, int p, int r){
    if (p < r) {
        int q = (p + r) / 2;
        mergeSort(nums, p, q);
        mergeSort(nums, q + 1, r);
        merge(nums, p, q, r);
    }
}
void merge(vector<int>& nums, int p, int q, int r) {
    int s1 = p, s2 = q + 1;
    vector<int> l1, l2;
    for (int i = s1; i <= q; i++) {
        l1.push_back(nums[i]);
    }
    for (int i = s2; i <= r; i++) {
        l2.push_back(nums[i]);
    }
    int left = 0, right = 0;
    int idx = p; // 关键修改：从p开始而非0
    while (left < l1.size() && right < l2.size()) {
        if (l1[left] < l2[right]) {
            nums[idx] = l1[left++];
        }
        else {
            nums[idx] = l2[right++];
        }
        idx++;
    }
    while (left < l1.size()) {
        nums[idx++] = l1[left++];
    }
    while (right < l2.size()) {
        nums[idx++] = l2[right++];
    }
}

int main() {
    vector<int> vect;
    vect.push_back(1);
    vect.push_back(3);
    vect.push_back(12);
    vect.push_back(23);
    vect.push_back(4);
    vect.push_back(11);
    vect.push_back(44);
    vect.push_back(322);
    mergeSort(vect, 0, vect.size() - 1);
    for (int i = 0; i < vect.size(); i++) {
        cout << vect[i] << endl;
    }
    return 0;
}

运行修复后的代码，输出会是正确的排序结果：

1
3
4
11
12
23
44
322

内容的提问来源于stack exchange，提问作者Andybacis