洛谷 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;
}

// 数据生成器（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;
}