为什么这个合并排序实现不能正常工作？

Question

以下是我的归并排序实现，它所做的是获取一个整数对数组并根据对中的第二个元素对它们进行排序（关系被对中的第一个元素打破并且所有元素都不同）

void mer(vector<pair<int, int>> a, int l, int m, int r, vector<pair<int, int>> res) {
    int i = l;
    int j = m;
    int k = l;
    while (i < m && j < r) {
        if (a[i].second < a[j].second) {
            res[k] = a[i];
            i++;
            k++;
        } else
        if (a[i].second > a[j].second) {
            res[k] = a[j];
            j++;
            k++;
        } else {
            if (a[i].first > a[j].first) {
                res[k] = a[j];
                k++;
                j++;
            } else {
                res[k] = a[i];
                i++;
                k++;
            }
        }
    }
    while (i < m) {
        res[k] = a[i];
        k++;
        i++;
    }
    while (j < r) {
        res[k] = a[j];
        k++;
        j++;
    }
    for (int i = l; i < r; i++) {
        a[i] = res[i];
    }
}
    
void solve(vector<pair<int, int>> a, int l, int r, vector<pair<int, int>> res) {
    if (l < r) {
        int m = (l + r) / 2;
        solve(a, l, m, res);
        solve(a, m + 1, r, res);
        mer(a, l, m, r, res);
    }
}

但是当我运行我的代码 main:

int main() {
    int n;
    cin >> n;
    map<int, int> a;

    for (int i = 0; i < n; i++) {
        int u;
        cin >> u;
        a[u]++;
    }
    vector<pair<int, int>> b;
    for (auto i : a) {
        b.push_back(i);
    }
    vector<pair<int, int>> res(b.size());
    solve(b, 0, b.size(), res);
}

考虑我的输入是：

10
1 1 1 1 1 1 2 2 3 3
it outputs 
1 6
2 2
3 2

那就是输入输出都是一样的。我花了很多时间寻找问题。我无法修复它。

Answer 1

您的代码中存在多个问题：

vector 对象应该通过引用传递。
res 不是 solve() 函数的目的地，而是充当 mer 临时存储的辅助向量。称它为 tmp 会更容易混淆。

排除了solve()中的r索引，所以对于少于2个元素的切片的测试和递归调用应该是：

void mer(vector<pair<int, int>>& a, int l, int m, int r, vector<pair<int, int>>& res) {
    int i = l;
    int j = m;
    int k = l;
    while (i < m && j < r) {
        if (a[i].second < a[j].second) {
            res[k] = a[i];
            i++;
            k++;
        } else
        if (a[i].second > a[j].second) {
            res[k] = a[j];
            j++;
            k++;
        } else {
            if (a[i].first > a[j].first) {
                res[k] = a[j];
                k++;
                j++;
            } else {
                res[k] = a[i];
                i++;
                k++;
            }
        }
    }
    while (i < m) {
        res[k] = a[i];
        k++;
        i++;
    }
    while (j < r) {
        res[k] = a[j];
        k++;
        j++;
    }
    for (int i = l; i < r; i++) {
        a[i] = res[i];
    }
}

void solve(vector<pair<int, int>>& a, int l, int r, vector<pair<int, int>>& tmp) {
    if (r - l >= 2) {
        int m = (l + r) / 2;
        solve(a, l, m, tmp);
        solve(a, m, r, tmp);
        mer(a, l, m, r, tmp);
    }
}

在 main() 函数中，您没有将输入值存储到对向量中，您还应该打印排序后的对：

int main() {
    int n;
    cin >> n;

    vector<pair<int, int>> a(n);

    for (int i = 0; i < n; i++) {
        a[i].first = i + 1;
        cin >> a[i].second;
    }
    vector<pair<int, int>> tmp(n);
    solve(a, 0, n, tmp);
    for (int i = 0; i < n; i++) {
        printf("%d %d\n", a[i].first, a[i].second);
    }
    return 0
}

为什么这个合并排序实现不能正常工作？

Why is this merge sort implementation not working properly?

c++

sorting

mergesort