洛谷 P1177 【模板】排序

// P1177 【模板】排序 —— ★ 这一版就能 AC：sort 一行
//
// 比赛里排序就写这一行，没有第二个选项。这一页存在的理由**不是**教你手写排序，
// 而是回答一个具体的问题：**手写快排交上去为什么会 TLE？**
//
// ⚠ 读入 10⁵ 个数，`cin` 关掉同步就够了（第 8 章 P2249 那页量过同一件事）。

#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<int> 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 + 1 == n];
    return 0;
}

// P1177 的第一版：冒泡 —— 大多数人真实的第一个排序算法
//
// 它当然是对的。问题是 O(n²)：n = 10⁵ ⇒ **10¹⁰ 次比较**。
// 按本机实测的速率（见 p1177Count.cpp）外推，要跑十几秒，而时限是 1 秒。
//
// ⚠ 这份代码带一个「这一趟有没有换过」的提前退出 ——
//   ★ 它让**已经有序**的数据变成 O(n)，但对随机数据一点用都没有。
//   ⇒ 「加了个优化」和「复杂度变了」是两回事，见第 7 章 P1147 那条。

#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<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) {
        bool swapped = false;
        for (int j = 0; j + 1 + i < n; 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 + 1 == n];
    return 0;
}

// ⚠ 故意写错的（其实是「写得太天真」）：手写快排，pivot 取**第一个元素**
//
//     int pivot = a[l];       ← 教科书上最常见的写法
//
// ★★★ 它**答案完全正确**，但在两种数据上退化成 O(n²)：
//   ① **已经有序**（或倒序）：每次划分只能切掉一个元素 ⇒ 递归 n 层；
//   ② **所有数都相同**：单向 partition 会把所有元素都堆到一边。
//
// ⚠ 而这两种数据一点都不罕见 —— 洛谷 P1177 的数据里就有。
//   「我手写的快排在本地跑得飞快，交上去 TLE」十有八九就是它。
//
// ⚠ 还有一个更凶的后果：递归 n 层 ⇒ **爆栈**（第 30 章实测本机 8 MB 栈约 28 万层）。
//   n = 10⁵ 还撑得住，再大就直接段错误 —— 而段错误看起来完全不像「排序写错了」。

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

static vector<int> a;
static long long cmps;                          // 数一数比较了多少次

static void qsort_(int l, int r) {
    if (l >= r) return;
    int pivot = a[l], i = l, j = r;             // ⚠ 就是这一行
    while (i < j) {
        while (i < j && (cmps++, a[j] >= pivot)) j--;
        a[i] = a[j];
        while (i < j && (cmps++, a[i] <= pivot)) i++;
        a[j] = a[i];
    }
    a[i] = pivot;
    qsort_(l, i - 1);
    qsort_(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];
    qsort_(0, n - 1);
    for (int i = 0; i < n; i++) cout << a[i] << " \n"[i + 1 == n];
    return 0;
}

// 换一把尺子：两种 pivot 各在什么数据上退化
//
// 用法：./p1177Count [n]          人话版（带秒表）
//       ./p1177Count [n] csv      只打 `键,值`，给 check:viz 用
//
// 四种数据（都是 n 个数）：
//   ① 随机   ② **已经升序**   ③ **完全倒序**   ④ **所有数都相同**
//
// 两种写法：
//   · `bad`  = pivot 取第一个元素 + 单向 partition（p1177QuickBad.cpp 那一版）
//   · `good` = pivot 随机取 + 三路划分（p1177Quick.cpp 那一版）
//
// ★ 数的是**比较次数**，因为秒表在小数据上量不动，而在大数据上 bad 那版直接爆栈。
// ⚠ 所以 n 默认取 20000：这个规模下 bad 版的递归深度（有序数据上就是 n）
//   还没到爆栈线（本机约 28 万层），量得出来又不会崩。

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

static vector<int> a;
static long long cmps;
static int depth_, maxDepth;

/* p1177QuickBad.cpp 那一版：pivot = a[l]，单向 partition */
static void qbad(int l, int r) {
    if (l >= r) return;
    depth_++; maxDepth = max(maxDepth, depth_);
    int pivot = a[l], i = l, j = r;
    while (i < j) {
        while (i < j && (cmps++, a[j] >= pivot)) j--;
        a[i] = a[j];
        while (i < j && (cmps++, a[i] <= pivot)) i++;
        a[j] = a[i];
    }
    a[i] = pivot;
    qbad(l, i - 1);
    qbad(i + 1, r);
    depth_--;
}

/* p1177Quick.cpp 那一版：随机 pivot + 三路划分 + 短的先递归 */
static mt19937 rng(20260827u);
static void qgood(int l, int r) {
    while (l < r) {
        depth_++; maxDepth = max(maxDepth, depth_);
        int pivot = a[l + (int)(rng() % (unsigned)(r - l + 1))];
        int lt = l, i = l, gt = r;
        while (i <= gt) {
            cmps++;
            if (a[i] < pivot) swap(a[lt++], a[i++]);
            else if (cmps++, a[i] > pivot) swap(a[i], a[gt--]);
            else i++;
        }
        if (lt - l < r - gt) { qgood(l, lt - 1); l = gt + 1; }
        else { qgood(gt + 1, r); r = lt - 1; }
        depth_--;
    }
}

static void makeData(int n, int shape) {
    a.assign(n, 0);
    mt19937 g(12345u);
    for (int i = 0; i < n; i++) {
        if (shape == 0) a[i] = (int)(g() % 1000000000u) + 1;
        else if (shape == 1) a[i] = i + 1;
        else if (shape == 2) a[i] = n - i;
        else a[i] = 7;
    }
}

int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 20000;
    bool csv = (argc > 2 && string(argv[2]) == "csv");
    const char* name[4] = { "随机", "已经升序", "完全倒序", "所有数都相同" };
    long long badC[4], goodC[4];
    int badD[4], goodD[4];
    double badMs[4], goodMs[4];

    for (int s = 0; s < 4; s++) {
        makeData(n, s);
        cmps = 0; depth_ = 0; maxDepth = 0;
        auto t0 = steady_clock::now();
        qbad(0, n - 1);
        badMs[s] = duration<double, milli>(steady_clock::now() - t0).count();
        badC[s] = cmps; badD[s] = maxDepth;

        makeData(n, s);
        cmps = 0; depth_ = 0; maxDepth = 0;
        t0 = steady_clock::now();
        qgood(0, n - 1);
        goodMs[s] = duration<double, milli>(steady_clock::now() - t0).count();
        goodC[s] = cmps; goodD[s] = maxDepth;
    }

    if (csv) {
        printf("n,%d\n", n);
        for (int s = 0; s < 4; s++)
            printf("bad%d,%lld\ngood%d,%lld\nbadDepth%d,%d\ngoodDepth%d,%d\nratio%d,%lld\nbadFaster%d,%d\n",
                   s, badC[s], s, goodC[s], s, badD[s], s, goodD[s], s, badC[s] / max(1LL, goodC[s]),
                   s, (badMs[s] < goodMs[s]) ? 1 : 0);
        return 0;
    }
    printf("n = %d，两种 pivot 各要比较多少次：\n\n", n);
    printf("  %-16s %14s %14s %10s   %8s %8s   %9s\n",
           "数据", "pivot=首元素", "pivot 随机", "次数之比", "深度(坏)", "深度(好)", "秒表(坏)");
    for (int s = 0; s < 4; s++) {
        string t = name[s];
        int w = 0; for (unsigned char c : t) { if ((c & 0xC0) == 0x80) continue; w += (c < 0x80) ? 1 : 2; }
        printf("  %s%*s %14lld %14lld %9.2f×   %8d %8d   %7.1f ms\n", t.c_str(), max(0, 16 - w), "",
               badC[s], goodC[s], (double)badC[s] / (double)max(1LL, goodC[s]), badD[s], goodD[s], badMs[s]);
    }
    printf("\n  ★★★ 「随机」那一行 pivot=首元素**反而更少** —— 本地随手测，它是赢的。\n");
    printf("  ★★★ 而下面三行是**同一份代码**在别的数据上的样子。\n");
    printf("  ⚠ 看「深度(坏)」那一列：有序数据上递归 %d 层，n 再大一个量级就是段错误。\n", badD[1]);
    return 0;
}

// 手写快排 —— 能过的那一版：pivot **随机取**
//
//     int pivot = a[l + rng() % (r - l + 1)];
//
// ★ 一行之差，上一版那两种「杀手数据」全部失效：
//   对手（出题人）不知道你的随机数，就构造不出必然退化的输入。
//   ⇒ **随机化不是让算法变快，是让「最坏情况」变得不可预谋。**
//
// ⚠ 全相同元素那一档，光靠随机 pivot **还不够** —— 单向 partition 仍然会把
//   所有元素堆到一边。这里用的是**三路划分**（小于 / 等于 / 大于），
//   等于 pivot 的那一段直接不用再递归。
//   ★ 这也是为什么 `std::sort` 不是教科书快排：它是 introsort
//     （快排 + 递归太深就转堆排 + 小段插入排序）。

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

static vector<int> a;
static mt19937 rng(20260827u);

static void qsort_(int l, int r) {
    while (l < r) {
        int pivot = a[l + (int)(rng() % (unsigned)(r - l + 1))];
        int lt = l, i = l, gt = r;              // [l,lt) < pivot, [lt,i) == pivot, (gt,r] > pivot
        while (i <= gt) {
            if (a[i] < pivot) swap(a[lt++], a[i++]);
            else if (a[i] > pivot) swap(a[i], a[gt--]);
            else i++;
        }
        /* ★ 先递归短的那一半，长的那半用循环 ⇒ 递归深度稳定在 O(log n)，爆不了栈 */
        if (lt - l < r - gt) { qsort_(l, lt - 1); l = gt + 1; }
        else { qsort_(gt + 1, r); r = lt - 1; }
    }
}

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];
    qsort_(0, n - 1);
    for (int i = 0; i < n; i++) cout << a[i] << " \n"[i + 1 == n];
    return 0;
}

// ★ 第 37 章的补课：**堆排序** —— 建堆 O(n) + n 次「取最大」，而且**完全原地**
//
// ============ 它和前面几版的关系 ============
//   这一页前面量过：pivot 取首元素的手写快排在**有序数据**上要比较 2×10⁸ 次（354 倍）、
//   递归 19 999 层。救它要两处改动（随机 pivot ＋ 三路划分）。
//   ★★ 而堆排序**根本不需要救** —— 它的 O(n log n) 是**最坏情况**的保证，
//     不是平均情况的：数据长什么样，它的比较次数几乎一模一样（第 ⑥ 步那张表）。
//
// ============ 两步 ============
//   ① **建堆**：从最后一个非叶子结点往前，逐个 down —— [第 37 章第 11 步]证过这是 O(n)；
//   ② **n 次取最大**：把堆顶和最后一格交换、堆长度减一、再 down 一次
//      ⇒ 最大的落到最后、次大的落到倒数第二…… 跑完就是升序。
//
// ★ 「原地、不要额外空间」正是这么来的：**被弹出去的元素就存在数组尾巴上**，
//   一个字节的额外空间都不用（对照 std::sort 的 introsort 也要 O(log n) 的栈）。
// ⚠ 而它在实战里通常比 std::sort 慢 —— 原因不在次数上，在 cache 上（第 ⑥ 步）。

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

static int a[100005];

/** 下沉：两个儿子里挑**大**的换（这里建的是大根堆） */
static void down(int i, int len) {
    int x = a[i];
    while ((i << 1) + 1 < len) {
        int c = (i << 1) + 1;                        // 0 基：儿子是 2i+1 / 2i+2
        if (c + 1 < len && a[c + 1] > a[c]) c++;
        if (a[c] <= x) break;
        a[i] = a[c];
        i = c;
    }
    a[i] = x;
}

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

    int n;
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = n / 2 - 1; i >= 0; i--) down(i, n);  // ① 建堆，O(n)
    for (int len = n; len > 1; len--) {               // ② n 次取最大
        swap(a[0], a[len - 1]);
        down(0, len - 1);
    }

    string out;
    for (int i = 0; i < n; i++) { if (i) out += ' '; out += to_string(a[i]); }
    out += '\n';
    cout << out;
    return 0;
}

// ★ 第 37 章补课那一节的度量：**堆排序在四种数据上稳不稳**
//
// 用法：./p1177HeapCount [n]          人话版（带秒表）
//       ./p1177HeapCount [n] csv      只打 `键,值`，给 check:viz 用
//
// 四种数据和 p1177Count.cpp 完全一样：① 随机 ② 已经升序 ③ 完全倒序 ④ 所有数都相同。
// 量三件事：
//   · 堆排序的**比较次数**（和 p1177Count 里两种快排那张表并排看）
//   · ★★ 前**三**档（随机 / 升序 / 倒序）之间的**最大 / 最小之比** ——
//     这一个数就是「它对数据形状免疫」的全部证据（快排那张表同一列是 4999 倍）。
//     ⚠ 第四档「所有数都相同」要单独看：那一档堆排序**反而更快**（一次 down 走一步就停），
//     它不是退化，是白捡的便宜 —— **别把它混进那个比值里**。
//   · 秒表：堆排序 vs std::sort（⚠ 次数少不等于跑得快 —— 差在 cache 上）
//
// ⚠⚠ 2026-08-31 修：秒表那一列原来是**单次** n = 20000 的排序（两边都只有零点几毫秒），
//   在 `npm run check` 那种 8 路并行的环境里量的基本是噪声 —— 于是 `slower` 那个断言
//   在全量里翻红过一次（`--ch=10` 单跑却是绿的）。现在改成**重复 REP 次取平均**。
//   ★ 机器闲下来重量的结果（A 机 · WSL2 · 2026-08-31 · REP = 50）：
//     随机 1.29 ms / 升序 0.76 / 倒序 0.78 / 全相同 0.04，而 std::sort 是 0.78 / 0.09 / 0.07 / 0.07
//     ⇒ 随机那一档堆排序慢 **1.7 倍**，而「所有数都相同」那一档它**反而更快**。
//   ★ 顺带量了一件本来该先问的事：**cmps++ 那个插桩本身贵多少** —— 1.33 vs 1.29 ms，
//     只有 3%，所以拿「带计数的堆排序」去和「没插桩的 std::sort」比秒表是公平的。
//     ⚠ 但这句话是**量出来才敢说**的，不是想当然。
//
// ⚠ 堆排序是**迭代**的，没有递归深度这一列（快排那版在有序数据上是 19 999 层）。

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

static vector<int> a;
static long long cmps;

static void down(int i, int len) {
    int x = a[i];
    while ((i << 1) + 1 < len) {
        int c = (i << 1) + 1;
        if (c + 1 < len && (cmps++, a[c + 1] > a[c])) c++;
        if ((cmps++, a[c] <= x)) break;
        a[i] = a[c];
        i = c;
    }
    a[i] = x;
}
static void heapSort(int n) {
    for (int i = n / 2 - 1; i >= 0; i--) down(i, n);
    for (int len = n; len > 1; len--) { swap(a[0], a[len - 1]); down(0, len - 1); }
}
static void makeData(int n, int shape) {
    a.assign(n, 0);
    mt19937 g(12345u);                               // ⚠ 和 p1177Count.cpp 同一个种子
    for (int i = 0; i < n; i++) {
        if (shape == 0) a[i] = (int)(g() % 1000000000u) + 1;
        else if (shape == 1) a[i] = i + 1;
        else if (shape == 2) a[i] = n - i;
        else a[i] = 7;
    }
}

int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 20000;
    bool csv = (argc > 2 && string(argv[2]) == "csv");
    const int REP = 20;                              // ★ 单次只有零点几毫秒 ⇒ 必须重复取平均
    const char* name[4] = { "随机", "已经升序", "完全倒序", "所有数都相同" };
    long long heapC[4];
    double heapMs[4], sortMs[4];
    int ok = 1;

    for (int s = 0; s < 4; s++) {
        makeData(n, s);
        vector<int> want = a;
        sort(want.begin(), want.end());

        double hs = 0, ss = 0;
        for (int r = 0; r < REP; r++) {
            makeData(n, s);
            cmps = 0;
            auto t0 = steady_clock::now();
            heapSort(n);
            hs += duration<double, milli>(steady_clock::now() - t0).count();
            if (a != want) ok = 0;                   // ★ 先钉死「它是对的」，再谈快慢

            makeData(n, s);
            t0 = steady_clock::now();
            sort(a.begin(), a.end());
            ss += duration<double, milli>(steady_clock::now() - t0).count();
        }
        heapMs[s] = hs / REP;
        sortMs[s] = ss / REP;
        heapC[s] = cmps;                             // 比较次数和轮数无关，取最后一轮的即可
    }

    long long mx = *max_element(heapC, heapC + 3), mn = *min_element(heapC, heapC + 3);   // ⚠ 只看前三档

    if (csv) {
        printf("n,%d\n", n);
        for (int s = 0; s < 4; s++) printf("heap%d,%lld\n", s, heapC[s]);
        printf("spread,%lld,%lld,%lld\n", mx, mn, heapC[3]);
        printf("ok,%d\n", ok);
        printf("slower,%d\n", (heapMs[0] > sortMs[0]) ? 1 : 0);
        return 0;
    }
    printf("n = %d，堆排序在四种数据上的比较次数：\n\n", n);
    printf("  %-16s %14s %12s %12s\n", "数据", "堆排序比较次数", "堆排序", "std::sort");
    for (int s = 0; s < 4; s++) {
        string t = name[s];
        int w = 0; for (unsigned char c : t) { if ((c & 0xC0) == 0x80) continue; w += (c < 0x80) ? 1 : 2; }
        printf("  %s%*s %14lld %10.1f ms %10.1f ms\n", t.c_str(), max(0, 16 - w), "",
               heapC[s], heapMs[s], sortMs[s]);
    }
    printf("\n  ★★ 前三档的最大 / 最小之比 = %lld / %lld = %.3f —— **它对数据形状几乎免疫**\n",
           mx, mn, (double)mx / (double)mn);
    printf("  ⚠ 第四档「所有数都相同」只有 %lld 次 —— 那是白捡的便宜，不是退化\n", heapC[3]);
    printf("  ★ 四档排序结果都正确：%s\n", ok ? "是" : "否");
    return 0;
}

// 数据生成器（P1177 对拍用）：`./p1177Gen <seed> [shape]`
//
//   shape 0（默认）随机
//   shape 1        已经升序      ← p1177QuickBad 的杀手之一
//   shape 2        完全倒序      ← 同上
//   shape 3        所有数都相同  ← 单向 partition 的杀手
//   shape 4        只有两三种取值（大量重复，但不是全相同）
//
// ⚠ 这几档**抓不到任何「答案错」** —— 四个版本在所有档位上答案都一样。
//   它们要抓的是**复杂度**，而复杂度得靠 p1177Count.cpp 数次数
//   （第 53 章那条：有一类 bug 只坏复杂度、不坏答案，对拍永远不说话）。
//   ⇒ 那这个生成器还有什么用？**用来证明「答案确实都一样」** ——
//     不先钉死这一条，「只是慢」这个结论本身就是没根据的。

#include <bits/stdc++.h>
using namespace std;
static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }

int main(int argc, char** argv) {
    rng.seed((argc > 1) ? (unsigned)atoi(argv[1]) : 1);
    int shape = (argc > 2) ? atoi(argv[2]) : 0;
    int n = ri(1, 30);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        if (shape == 1) a[i] = i + 1;
        else if (shape == 2) a[i] = n - i;
        else if (shape == 3) a[i] = 7;
        else if (shape == 4) a[i] = ri(1, 3);
        else a[i] = ri(1, 1000000000);
    }
    printf("%d\n", n);
    for (int i = 0; i < n; i++) printf("%d%c", a[i], i + 1 == n ? '\n' : ' ');
    return 0;
}

// 顶格数据（P1177 计时用）：`./p1177GenBig <n> [shape]`
//
//   shape 0 随机 / 1 已经升序 / 2 完全倒序 / 3 全相同
// ⚠ 题面：1 <= N <= 10⁵，1 <= a_i <= 10⁹。默认就按顶格来。

#include <bits/stdc++.h>
using namespace std;
int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 100000;
    int shape = (argc > 2) ? atoi(argv[2]) : 0;
    mt19937 rng(20260827u);
    printf("%d\n", n);
    for (int i = 0; i < n; i++) {
        int v;
        if (shape == 1) v = i + 1;
        else if (shape == 2) v = n - i;
        else if (shape == 3) v = 7;
        else v = (int)(rng() % 1000000000u) + 1;
        printf("%d%c", v, i + 1 == n ? '\n' : ' ');
    }
    return 0;
}