P1177 【模板】排序

题目描述

将读入的 \(N\) 个数从小到大排序后输出。

输入格式

第一行为一个正整数 \(N\)。

第二行包含 \(N\) 个空格隔开的正整数 \(a_i\)，为你需要进行排序的数。

输出格式

将给定的 \(N\) 个数从小到大输出，数之间空格隔开。

输入输出样例 #1

输入 #1

5
4 2 4 5 1

输出 #1

1 2 4 4 5

说明/提示

对于 \(20\%\) 的数据，有 \(1 \leq N \leq 10^3\)；

对于 \(100\%\) 的数据，有 \(1 \leq N \leq 10^5\)，\(1 \le a_i \le 10^9\)。

好，这题是排序模板题 + 快排实现，我按你刚定的格式来👇

---

Tip

建议看看这个博客里的内容：csdn文章
或者b站视频博主蓝不过海呀的讲解视频: b站蓝不过海呀

---

📌 题目分析

👉 本质： 把一个数组按从小到大排序

👉 类型： 排序算法（快速排序）

---

🧠 解题思路

1️⃣ 核心建模

输入一个数组 a[i]，要求：

按升序排列

2️⃣ 性质分析

👉 排序问题的常见解法：

• 快速排序（本题要求）
• 归并排序
• STL sort（底层快排+优化）

👉 这里重点：手写快速排序

3️⃣ 算法选择（快速排序）

核心思想：

选一个基准（pivot）
把数组分成：
左边 ≤ pivot
右边 ≥ pivot
递归处理两边

4️⃣ 快排核心步骤（必须掌握）

假设区间 [l, r]

✔ 1. 选基准

int pivot = a[(l + r) >> 1];

✔ 2. 双指针分区

int i = l, j = r;

while (i <= j) {
    while (a[i] < pivot) i++;
    while (a[j] > pivot) j--;
    if (i <= j) {
        swap(a[i], a[j]);
        i++, j--;
    }
}

✔ 3. 递归

if (l < j) quick_sort(l, j);
if (i < r) quick_sort(i, r);

5️⃣ 关键细节（非常重要）

• pivot 选中间 → 防止退化
• 必须 i <= j（不是 <）
• 递归边界不能写错
• 数据量 1e5 → 快排 OK

6️⃣ 时间复杂度

• 平均：O(n log n) ✅
• 最坏：O(n^2)（已通过 pivot 优化降低概率）

---

💻 C++代码（手写快排）

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

const int N = 1e5 + 5;
int a[N];
int n;

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

    int i = l, j = r;
    int pivot = a[(l + r) >> 1]; // 选中间值

    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) {
            swap(a[i], a[j]);
            i++, j--;
        }
    }

    if (l < j) quick_sort(l, j);
    if (i < r) quick_sort(i, r);
}

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

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

    quick_sort(0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }

    return 0;
}

---

⚠️ 易错点

❌ 1. 死循环

while (i < j) ❌

✅ 必须：

while (i <= j)

❌ 2. 递归区间写错

quick_sort(l, i); ❌
quick_sort(j, r); ❌

✅ 正确：

quick_sort(l, j);
quick_sort(i, r);

❌ 3. pivot 选错

pivot = a[l]; ❌（容易退化）

✅ 推荐：

pivot = a[(l + r) >> 1];

❌ 4. 忘记边界判断

if (l >= r) return;