交付四种排序加一份对比

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

这是这条路线的最终作品。冒泡、插入、归并、堆排、计数、快排深度、选型都已经写好，只剩插入排序的内层和堆排序的第二步。补全之后一次验完五条：四种排序都等于 std::sort 的结果；冒泡比较 10 次、插入 8 次；稳定归并排四条记录得到小满/南风/阿岚/阿泰；快排在已排序数组上深度是 5；数据基本有序选插入排序。五条全过输出 验收通过，否则输出 验收失败。

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

提交你的答案

请登录后提交答案。

去登录

← 第四步稳定性对比修排序 bug 时先怎么自测 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

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

vector<int> bubble(vector<int> b) {
    int n = (int)b.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (b[j] > b[j + 1]) swap(b[j], b[j + 1]);
        }
    }
    return b;
}

vector<int> insertion(vector<int> b) {
    for (int i = 1; i < (int)b.size(); i++) {
        int key = b[i];
        int j = i - 1;
        // TODO: 前面比 key 大的都往后挪一格，最后把 key 放进 b[j + 1]
        (void)key;
        (void)j;
    }
    return b;
}

vector<int> merge_two(const vector<int>& left, const vector<int>& right) {
    vector<int> out;
    size_t i = 0, j = 0;
    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j]) out.push_back(left[i++]);
        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<int> msort(const vector<int>& a) {
    if (a.size() <= 1) return a;
    size_t m = a.size() / 2;
    vector<int> l(a.begin(), a.begin() + m), r(a.begin() + m, a.end());
    return merge_two(msort(l), msort(r));
}

void sift_down(vector<int>& h, int i, int n) {
    while (true) {
        int big = i;
        int l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && h[l] > h[big]) big = l;
        if (r < n && h[r] > h[big]) big = r;
        if (big == i) return;
        swap(h[i], h[big]);
        i = big;
    }
}

vector<int> hsort(vector<int> h) {
    int n = (int)h.size();
    for (int i = n / 2 - 1; i >= 0; i--) sift_down(h, i, n);
    // TODO: 从末尾往前：交换 h[0] 和 h[end]，再在前 end 个里下沉
    return h;
}

int bubble_cmps(vector<int> b) {
    int n = (int)b.size(), cmps = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            cmps++;
            if (b[j] > b[j + 1]) swap(b[j], b[j + 1]);
        }
    }
    return cmps;
}

int insert_cmps(vector<int> b) {
    int cmps = 0;
    for (int i = 1; i < (int)b.size(); i++) {
        int key = b[i];
        int j = i - 1;
        while (j >= 0) {
            cmps++;
            if (b[j] <= key) break;
            b[j + 1] = b[j];
            j--;
        }
        b[j + 1] = key;
    }
    return cmps;
}

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++]);
        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));
}

string pick(const string& need) {
    const map<string, string> table = {
        {"数据基本有序", "插入排序"},
        {"要求稳定且数据量大", "归并排序"},
        {"内存吃紧不能另开数组", "堆排序"},
        {"一般情况", "标准库 sort"},
    };
    auto it = table.find(need);
    if (it == table.end()) return "还得再想想";
    return it->second;
}

int MAXD = 0;

void quick_d(const vector<int>& a, int d) {
    MAXD = max(MAXD, d);
    if (a.size() <= 1) return;
    int pivot = a.back();
    vector<int> less, more;
    for (size_t k = 0; k + 1 < a.size(); k++) {
        if (a[k] < pivot) less.push_back(a[k]);
        else more.push_back(a[k]);
    }
    quick_d(less, d + 1);
    quick_d(more, d + 1);
}

int main() {
    vector<int> a = {17, 24, 15, 13, 23};
    vector<int> s = a;
    sort(s.begin(), s.end());
    vector<bool> checks;
    checks.push_back(bubble(a) == s && insertion(a) == s && msort(a) == s && hsort(a) == s);
    checks.push_back(bubble_cmps(a) == 10 && insert_cmps(a) == 8);
    vector<Rec> rows(ROWS.begin(), ROWS.end());
    checks.push_back(names(msort_rec(rows)) == "小满/南风/阿岚/阿泰");
    quick_d({13, 15, 17, 23, 24}, 1);
    checks.push_back(MAXD == 5);
    checks.push_back(pick("数据基本有序") == "插入排序");
    bool ok = true;
    for (bool c : checks) ok = ok && c;
    cout << (ok ? "验收通过" : "验收失败") << endl;
}

本次输入：

输出：

👩‍🏫

AI

💬 题目评论

🔒 登录并作答后可看讨论