排序：冒泡 → 归并 → 快排

// 排序 —— 冒泡
//
// 输入：第一行 n，第二行 n 个整数
// 输出：从小到大排好序的 n 个数
//
// 冒泡的思路简单到不用解释：相邻两个如果左边比右边大，就交换。
// 扫一遍，最大的那个就「冒」到最右边了；再扫一遍，第二大的到位……扫 n 遍就排好了。
//
// 复杂度 O(n²)。n = 1000 时是一百万次比较（眨眼间），
// n = 50000 时是 25 亿次 —— 正文第 3 步会让你亲眼看它卡住。
//
// 那个 `if (!swapped) break;` 是一个常见的小优化：
// 如果一整趟下来一次都没换过，说明已经有序了，可以提前收工。
// 它能让「已经排好序」的数据变成 O(n)，但**改变不了最坏情况**（逆序输入还是 O(n²)）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        // 每一趟结束，最右边的 i 个已经就位，不用再看
        for (int j = 0; j + 1 < n - i; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;          // 一趟都没换过，说明已经有序
    }

    for (int i = 0; i < n; i++) cout << a[i] << " \n"[i == n - 1];
    return 0;
}

// 排序 —— 归并排序（手写）
//
// 输入输出和 bubble.cpp 完全一样。
//
// 这是第 2 章那句话最标准的一次现身：
//
//     **大问题 = 小问题 + 一步真活 + 小问题**
//
//     排 [l, r]  =  排左半边  +  把两个有序的半边合并起来  +  排右半边
//                   ↑小问题      ↑一步真活（这是唯一真正干活的地方）  ↑小问题
//
// 三要素还是那三个：
//   职责：mergeSort(l, r) 把 a[l..r] 排好序
//   边界：l >= r 时只有 0 或 1 个元素，本来就有序，直接返回
//   递推：先排好两半，再合并
//
// 合并两个有序数组为什么快？因为两边都是有序的，
// 只要各拿一根手指指着开头，每次比一下、取小的那个往前挪 —— 这就是第 7 章的双指针。
// 合并 n 个元素只要 O(n)。
//
// 复杂度：一共分 log n 层，每层合并的总量是 n，所以 O(n log n)。
//   n = 50000 时约 78 万次操作，而冒泡是 25 亿次 —— 差三千多倍。
//
// ⚠ 那个临时数组 tmp 不要写在函数里面。
//   写在里面的话每层递归都要新建一个 vector，光是分配内存就慢一大截。

#include <bits/stdc++.h>
using namespace std;

vector<long long> a, tmp;

void mergeSort(int l, int r) {
    if (l >= r) return;                       // 边界：0 或 1 个元素，天然有序

    int mid = l + (r - l) / 2;
    mergeSort(l, mid);                        // 排左半边（信任它）
    mergeSort(mid + 1, r);                    // 排右半边（信任它）

    // ---- 一步真活：把两个已经有序的半边合并起来 ----
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        // 注意是 <=：相等时优先取左边的，这样相等元素的相对顺序不变（稳定排序）
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];       // 左边有剩，直接搬过来
    while (j <= r)   tmp[k++] = a[j++];       // 右边有剩，同理

    for (int p = l; p <= r; p++) a[p] = tmp[p];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    a.assign(n, 0);
    tmp.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];

    if (n > 0) mergeSort(0, n - 1);

    for (int i = 0; i < n; i++) cout << a[i] << " \n"[i == n - 1];
    return 0;
}

// 排序 —— 快速排序（手写）
//
// 输入输出和 bubble.cpp 完全一样。
//
// 快排也是分治，但和归并**分工正好相反**：
//
//   归并：随便切成两半（一步真活在「合并」）
//   快排：先选一个基准，把小的甩到左边、大的甩到右边（一步真活在「划分」），
//         划分完之后两边各自排好，就整体有序了 —— 不需要合并。
//
// 一句话：**归并是「先分后治」，快排是「先治后分」。**
//
// ⚠ 基准（pivot）一定要随机选！
//   如果永远取第一个元素当基准，遇到**已经排好序**的数据，
//   每次划分都会切出「0 个 + n-1 个」这种最坏的形状，复杂度退化成 O(n²)。
//   而「已经排好序的数据」在真实测试数据里太常见了 ——
//   出题人甚至会专门造这种数据来卡不随机的快排。
//
//   随机选基准之后，退化的概率低到可以忽略（要连续几十次都倒霉才行）。
//
// 平均复杂度 O(n log n)，常数比归并小，所以标准库的 sort 底子就是它。

#include <bits/stdc++.h>
using namespace std;

vector<long long> a;
mt19937 rng(20241010u);          // 固定种子，保证同一份输入每次跑出来完全一样

void quickSort(int l, int r) {
    if (l >= r) return;

    // 随机挑一个基准，换到最左边
    int p = l + (int)(rng() % (unsigned)(r - l + 1));
    swap(a[l], a[p]);
    long long pivot = a[l];

    // Hoare 划分：两根指针从两头往中间夹（第 7 章的对撞双指针）
    int i = l, j = r;
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;   // 从右边找第一个 < pivot 的
        while (i < j && a[i] <= pivot) i++;   // 从左边找第一个 > pivot 的
        if (i < j) swap(a[i], a[j]);
    }
    swap(a[l], a[i]);                          // 基准归位，此刻 a[i] 就在它最终的位置上

    quickSort(l, i - 1);
    quickSort(i + 1, r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    a.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];

    if (n > 0) quickSort(0, n - 1);

    for (int i = 0; i < n; i++) cout << a[i] << " \n"[i == n - 1];
    return 0;
}

// 排序 —— 直接用 std::sort
//
// 输入输出和前面几份完全一样。
//
// 比赛里排序**一律用 sort**，别手写。理由很实在：
//   1. 它是内省排序（快排 + 堆排 + 插入排序的混合体），
//      递归太深时自动切换成堆排，**最坏情况也是 O(n log n)** —— 手写快排做不到这一点。
//   2. 它经过了极致的常数优化，比你手写的快。
//   3. 一行代码没有出错空间。
//
// 那为什么前面还要手写归并和快排？
//   因为**归并排序的那个「合并」是第 11 章求逆序对的核心**，
//   而快排的「划分」思想在很多题里会单独用到（比如求第 k 大）。
//   手写一遍是为了理解，比赛的时候用 sort。
//
// 记住排序的复杂度下界：基于比较的排序，最快就是 O(n log n)，
// 这是数学上证明过的，不存在「更聪明的比较排序」。
// （能突破这个下界的只有计数排序、基数排序那种不比较的方法，它们对数据有额外要求。）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a.begin(), a.end());                  // 就这一行

    for (int i = 0; i < n; i++) cout << a[i] << " \n"[i == n - 1];
    return 0;
}

// 排序 —— 归并排序（手写）
//
// 输入输出和 bubble.cpp 完全一样。
//
// 这是第 2 章那句话最标准的一次现身：
//
//     **大问题 = 小问题 + 一步真活 + 小问题**
//
//     排 [l, r]  =  排左半边  +  把两个有序的半边合并起来  +  排右半边
//                   ↑小问题      ↑一步真活（这是唯一真正干活的地方）  ↑小问题
//
// 三要素还是那三个：
//   职责：mergeSort(l, r) 把 a[l..r] 排好序
//   边界：l >= r 时只有 0 或 1 个元素，本来就有序，直接返回
//   递推：先排好两半，再合并
//
// 合并两个有序数组为什么快？因为两边都是有序的，
// 只要各拿一根手指指着开头，每次比一下、取小的那个往前挪 —— 这就是第 7 章的双指针。
// 合并 n 个元素只要 O(n)。
//
// 复杂度：一共分 log n 层，每层合并的总量是 n，所以 O(n log n)。
//   n = 50000 时约 78 万次操作，而冒泡是 25 亿次 —— 差三千多倍。
//
// ⚠ 那个临时数组 tmp 不要写在函数里面。
//   写在里面的话每层递归都要新建一个 vector，光是分配内存就慢一大截。

#include <bits/stdc++.h>
using namespace std;

vector<long long> a, tmp;

void mergeSort(int l, int r) {
    if (l >= r) return;                       // 边界：0 或 1 个元素，天然有序

    int mid = l + (r - l) / 2;
    mergeSort(l, mid);                        // 排左半边（信任它）
    mergeSort(mid + 1, r);                    // 排右半边（信任它）

    // ---- 一步真活：把两个已经有序的半边合并起来 ----
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        // 注意是 <=：相等时优先取左边的，这样相等元素的相对顺序不变（稳定排序）
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];       // 左边有剩，直接搬过来
    while (j <= r)   tmp[k++] = a[j++];       // 右边有剩，同理

    for (int p = l; p <= r; p++) a[p] = tmp[p];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    a.assign(n, 0);
    tmp.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];

    if (n > 0) mergeSort(0, n - 1);

    for (int i = 0; i < n; i++) cout << a[i] << " \n"[i == n - 1];
    return 0;
}

// 多关键字排序 —— sort + 自定义 cmp（正确写法）
//
// 输入输出和 studentBrute.cpp 完全一样。
//
// ============ cmp 函数的三条铁律 ============
//
// 1. **cmp(a, b) 的含义是「a 必须排在 b 前面吗」**，返回 true 就是要排前面。
//    不是「a 比 b 大吗」，也不是「要不要交换」。想不清楚就念一遍这句话。
//
// 2. **两个元素「一样」的时候必须返回 false。**
//    这是最要命的一条 —— 下一份 badcmp.cpp 会让你亲眼看到违反它的后果。
//    所以比较相等的情况时，用 `<` 和 `>`，**绝对不要用 `<=` 或 `>=`**。
//
// 3. **cmp 里不要写会改变外部状态的东西**（比如计数、输出）。
//    sort 内部会以未指定的顺序调用它任意多次。
//
// 多关键字的写法就是「上一个关键字分不出胜负时，才看下一个」：
//
//     if (a.score != b.score) return a.score > b.score;   // 第一关键字
//     return a.id < b.id;                                  // 第二关键字
//
// 注意最后一行**不带 if** —— 前面都相等了，这里必须给出确定的结论。

#include <bits/stdc++.h>
using namespace std;

struct Student { int id, score; };

bool cmp(const Student& a, const Student& b) {
    if (a.score != b.score) return a.score > b.score;   // 成绩高的在前（降序）
    return a.id < b.id;                                  // 成绩相同，学号小的在前（升序）
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<Student> v(n);
    for (int i = 0; i < n; i++) cin >> v[i].id >> v[i].score;

    sort(v.begin(), v.end(), cmp);

    for (int i = 0; i < n; i++) cout << v[i].id << " " << v[i].score << "\n";
    return 0;
}

// ⚠ 这是一份**故意写错**的 cmp —— 它会让 std::sort 直接崩溃
//
// 点「运行 ▶」跑一下。它多半会「异常退出」——
// 段错误、double free、堆损坏……具体是哪一种取决于运气，
// 但**基本不会**是「安安静静给你一个错误的排序结果」。
//
// 错在哪：`return a.score >= b.score;`  ——  多了一个等号。
//
// ============ 为什么一个等号能让程序崩溃 ============
//
// std::sort 要求 cmp 满足「严格弱序」，其中最关键的一条是：
//
//     **cmp(a, a) 必须是 false**（一个元素不可能排在自己前面）。
//
// 写成 `>=` 之后，cmp(a, a) 返回 true —— 在 sort 眼里，
// 「a 严格排在 a 前面」。这个矛盾会让它内部的插入排序**跑出数组边界**：
// 它一直往前找「比当前元素小的位置」，而在错误的 cmp 下这个条件永远成立，
// 于是指针一路冲出数组，读写到别人的内存上。
//
// 崩溃还算走运 —— 更糟的情况是**没崩，但悄悄改坏了别的变量**，
// 然后你在一个完全无关的地方看到诡异的结果，查一整天。
//
// ============ 记住这条规则 ============
//
//   **写 cmp 时，相等就必须返回 false。比较符只用 < 或 >，绝不用 <= 或 >=。**
//
// 这是 C++ 竞赛里最经典的一个「未定义行为」陷阱，几乎每个人都会踩一次。
// 现在踩，比在考场上踩好。

#include <bits/stdc++.h>
using namespace std;

struct Student { int id, score; };

bool badCmp(const Student& a, const Student& b) {
    return a.score >= b.score;         // ← 错！相等时返回了 true
}

int main() {
    // 造一批成绩大量重复的数据 —— 相等元素越多，这个错误暴露得越快
    const int n = 2000;
    vector<Student> v(n);
    mt19937 rng(12345);
    for (int i = 0; i < n; i++) { v[i].id = i + 1; v[i].score = (int)(rng() % 3); }

    cout << "拿 " << n << " 个学生（成绩只有 0/1/2 三种）去 sort，cmp 用的是 >= …\n";
    cout.flush();

    sort(v.begin(), v.end(), badCmp);   // ← 这里大概率就崩了

    cout << "居然没崩。但这不代表它是对的 —— 未定义行为的意思就是「什么都可能发生」，\n";
    cout << "换一组数据、换一个编译器、换一个优化等级，它随时会翻脸。\n";
    cout << "前 5 个：\n";
    for (int i = 0; i < 5 && i < n; i++) cout << "  " << v[i].id << " " << v[i].score << "\n";
    return 0;
}

// 多关键字排序 —— sort + 自定义 cmp（正确写法）
//
// 输入输出和 studentBrute.cpp 完全一样。
//
// ============ cmp 函数的三条铁律 ============
//
// 1. **cmp(a, b) 的含义是「a 必须排在 b 前面吗」**，返回 true 就是要排前面。
//    不是「a 比 b 大吗」，也不是「要不要交换」。想不清楚就念一遍这句话。
//
// 2. **两个元素「一样」的时候必须返回 false。**
//    这是最要命的一条 —— 下一份 badcmp.cpp 会让你亲眼看到违反它的后果。
//    所以比较相等的情况时，用 `<` 和 `>`，**绝对不要用 `<=` 或 `>=`**。
//
// 3. **cmp 里不要写会改变外部状态的东西**（比如计数、输出）。
//    sort 内部会以未指定的顺序调用它任意多次。
//
// 多关键字的写法就是「上一个关键字分不出胜负时，才看下一个」：
//
//     if (a.score != b.score) return a.score > b.score;   // 第一关键字
//     return a.id < b.id;                                  // 第二关键字
//
// 注意最后一行**不带 if** —— 前面都相等了，这里必须给出确定的结论。

#include <bits/stdc++.h>
using namespace std;

struct Student { int id, score; };

bool cmp(const Student& a, const Student& b) {
    if (a.score != b.score) return a.score > b.score;   // 成绩高的在前（降序）
    return a.id < b.id;                                  // 成绩相同，学号小的在前（升序）
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<Student> v(n);
    for (int i = 0; i < n; i++) cin >> v[i].id >> v[i].score;

    sort(v.begin(), v.end(), cmp);

    for (int i = 0; i < n; i++) cout << v[i].id << " " << v[i].score << "\n";
    return 0;
}