归并是稳定的吗

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

合并时，两边相等的元素先取左边那个（写成 <=），归并排序就是稳定的。补全后按 key 排四条记录（阿岚 2、小满 1、阿泰 2、南风 1），把名字按顺序用 / 拼起来输出。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 再把拆分接上归并和冒泡结果必须一样 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>
using namespace std;

struct Rec {
    string name;
    int key;
};

const vector<Rec> ROWS = {{"阿岚", 2}, {"小满", 1}, {"阿泰", 2}, {"南风", 1}};

string names(const vector<Rec>& v) {
    string s;
    for (size_t i = 0; i < v.size(); i++) s += (i ? "/" : "") + v[i].name;
    return s;
}

vector<Rec> merge_rec(const vector<Rec>& left, const vector<Rec>& right) {
    vector<Rec> out;
    size_t i = 0, j = 0;
    while (i < left.size() && j < right.size()) {
        if (left[i].key < right[j].key) out.push_back(left[i++]);  // TODO: 相等时要先取左边那个，才叫稳定
        else out.push_back(right[j++]);
    }
    while (i < left.size()) out.push_back(left[i++]);
    while (j < right.size()) out.push_back(right[j++]);
    return out;
}

vector<Rec> msort_rec(const vector<Rec>& a) {
    if (a.size() <= 1) return a;
    size_t m = a.size() / 2;
    vector<Rec> l(a.begin(), a.begin() + m), r(a.begin() + m, a.end());
    return merge_rec(msort_rec(l), msort_rec(r));
}

int main() {
    vector<Rec> rows(ROWS.begin(), ROWS.end());
    cout << names(msort_rec(rows)) << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

🔒 登录并作答后可看讨论