【GESP】C++四、五级练习题 luogu-P1177 【模板】排序

GESP C++ 四、五级以上水平练习题，考查快速排序知识点。四级要求掌握冒泡排序、插入排序、选择排序。但是实际编程应用中，一般都需要使用快速排序。本题应用四级的排序算法是无法通过的，因此建议四、五级以上考生练习。题目难度⭐⭐☆☆☆，洛谷难度等级普及−。

luogu-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$。

---

题目分析

这道题的核心考点是高效的排序算法，要求在短时间内将乱序的数组变为升序排列。在这里我们重点使用并分析经典的 快速排序 (Quick Sort) 算法。

1. 为什么需要快速排序？

题目中要求对最多 $N = 10^5$ 个数进行排序。如果使用初学阶段经常接触的冒泡排序、选择排序或插入排序等基础排序算法，它们的时间复杂度为 $O(N^2)$。在 $10^5$ 的数据规模下，最坏运算次数将达到 $10^{10}$ 次，绝对会导致程序在评测时出现 超时 (Time Limit Exceeded, TLE) 报错。

为了能够全对通过此题，我们需要平均时间复杂度为 $O(N \log N)$ 的高效排序算法。快速排序就是其中最常用、性能十分优秀的一种方案。

2. 快速排序的核心思想：分治法

快速排序利用了“分治法” (Divide and Conquer) 的思想。它的主要流程可以分解为三步：

1. 选择基准 (Pivot)：在待排序的区间中选取一个元素作为“基准”。为了防止在数组近乎有序时退化成 $O(N^2)$ 的最坏情况，示例代码中十分聪明地选取了区间中间的元素 target = ary[mid]。
2. 分割划分 (Partition)：这一步是快排的灵魂，即把所有比基准小的元素全部移动到基准的左边，所有比基准大（或等于）的元素移到右边。示例代码中采用了经典的“挖坑填数”法来实现这一过程。
3. 递归处理 (Recursion)：经过一次区间分割后，基准元素就被放置到了它最终应该所在的绝对正确的位置上。然后利用递归思想，再去毫无顾虑地分别对左半边区间和右半边区间进行同样的操作（直到子区间的数据只剩 1 个或 0 个）。

3. “挖坑填数”法实现细节

在示例代码中，我们结合双指针从前后端点向中间逼近的方式来实现分割：

• 将选出的基准 target 与区间的左端点对应的元素 ary[low] 互换，此时最左侧的位置 low 就可以看作是被挖出了一个“坑位”。
• 右指针先行：右指针 high 从右向左扫描寻找比 target 小的数。找到后，就把这个较小的数填入左侧的“坑” ary[low] 中，之后右侧的 high 位置就成为了新的“坑位”。
• 左指针跟上：左指针 low 开始从左向右扫描寻找比 target 大的数。找到后，便将其填入刚才右侧抛出的“坑” ary[high] 里面，填完后左侧的 low 再次成为新的“坑位”。
• 汇合归位：当左右指针相遇即 low == high 时，所有的位置都已经移动完毕，最后把最初选定的基准元素 target 填入最后的这个“坑位” ary[low] 中，宣告本次划分彻底大功告成。

---

示例代码

#include <iostream>

// 定义全局大数组，大小 100005，足够存题目指定的 N<=10^5 数据
int ary[100005];

// 快速排序算法 (Quick Sort)，平均时间复杂度 O(N log N)
void quickSort(int l, int r) {
    // 递归边界：当左侧边界大于等于右边界时，该区间段只剩1个或0个元素，自然是有序的
    if (l >= r) {
        return;
    }

    // 用 low 和 high 作为双指针从两端向中间逼近
    int low = l;
    int high = r;

    // 这里采用选取中间元素作为基准元素(pivot/target)的方式
    // 这种做法比单纯选第一个或最后一个更好，能在原始数组基本有序时防止退化到 O(N^2)
    int mid = l + (r - l) / 2;
    int target = ary[mid];

    // 将选出来的基准元素和左端点处的元素交换
    // 这样左端点 target(现在的 ary[low]) 就可以看作一个安全的“坑位”供后面填埋
    ary[mid] = ary[low];
    ary[low] = target;

    // 开始进行分割：比 target 小的元素移到其左边，比 target 大的元素移到右边
    while (low < high) {
        // 第一步：从右往左寻找比基准元素 target 小（或等于）的数
        while (low < high && ary[high] > target) {
            high--;
        }
        // 当找到后，把此时的 ary[high] 填入左侧低位留下来的“坑位”ary[low] 中
        if (low < high) {
            ary[low] = ary[high];
            low++;  // 填入后左指针前移一步，同时刚才挪走数据的 high成为新“坑位”
        }

        // 第二步：从左往右寻找比基准元素 target 大（或等于）的数
        while (low < high && ary[low] < target) {
            low++;
        }
        // 找到后将其填入右侧高位的“坑位”ary[high]中
        if (low < high) {
            ary[high] = ary[low];
            high--;  // 填入后右指针后移一步，同时刚才的 low 成为了新的“坑位”
        }
    }

    // 当前后指针相遇（low == high），这就是最终基准元素应该在的正确位置
    ary[low] = target;

    // 分治思想：以确定的基准元素所在位置 low 为界，分别递归排序其左半部分和右半部分
    quickSort(l, low - 1);
    quickSort(low + 1, r);
}

int main() {
    int N;
    // 读入元素总个数 N
    std::cin >> N;

    // 依次读入 N 个待排元素到全局数组
    for (int i = 0; i < N; i++) {
        std::cin >> ary[i];
    }

    // 调用最核心的快排函数，范围是从索引 0 开始，到 N-1 结束
    quickSort(0, N - 1);

    // 从小到大依次输出排序后的结果，每个数之后跟随一个空格
    for (int i = 0; i < N; i++) {
        std::cout << ary[i] << " ";
    }
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号