题解 - 【模板】排序 - Algo Beat Contest

题目大意

给定一个长度为 (n) 的序列 (a)，要求将其从小到大排序后输出。

数据范围

(1 \le n \le 10^5)
序列中的元素为整数，范围在 ([-10^9, 10^9]) 内
对于 (100%) 的数据，序列随机生成

解题思路

排序是最基础的算法问题，通常有几种经典解法：

调用库函数
在 C++ 中可直接使用 std::sort，在 Python 中可使用 list.sort() 或 sorted()。
这些库函数通常基于快速排序、堆排序或归并排序的混合实现，时间复杂度 (O(n \log n))，且常数小，代码简洁。
手写排序算法
若作为练习，可以选择实现：
- 快速排序：期望时间复杂度 (O(n \log n))，最坏 (O(n^2))（但数据随机，可接受）。
- 归并排序：稳定，时间复杂度稳定 (O(n \log n))，适合理解分治思想。
- 堆排序：原地排序，(O(n \log n))。

由于本题数据随机，且 (n \le 10^5)，任意 (O(n \log n)) 算法均可通过。

复杂度分析

时间复杂度：(O(n \log n))（基于比较的排序最优下界）
空间复杂度：
- 使用库函数（如 std::sort）通常为 (O(\log n)) 递归栈空间
- 归并排序需要额外 (O(n)) 空间
- 快速排序原地版本 (O(\log n)) 栈空间

代码实现

C++ 实现（使用 `std::sort`）

#include <iostream>
#include <vector>
#include <algorithm>

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

    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    std::sort(a.begin(), a.end());
    for (int i = 0; i < n; ++i) {
        std::cout << a[i] << " \n"[i == n - 1];
    }
    return 0;
}

Python 实现（使用 `sort` 方法）

n = int(input())
a = list(map(int, input().split()))
a.sort()
print(' '.join(map(str, a)))

手写快速排序（C++ 示例）

#include <iostream>
#include <vector>
using namespace std;

void quickSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int i = left, j = right, pivot = arr[left + (right - left) / 2];
    while (i <= j) {
        while (arr[i] < pivot) ++i;
        while (arr[j] > pivot) --j;
        if (i <= j) {
            swap(arr[i], arr[j]);
            ++i;
            --j;
        }
    }
    quickSort(arr, left, j);
    quickSort(arr, i, right);
}

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

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

总结

本题是排序模板题，直接调用语言内置排序函数即可通过。手写排序算法有助于加深对排序原理的理解，但考试或竞赛中优先使用库函数以避免不必要的错误。

注意：输入输出量较大时，建议使用快速 I/O（如 C++ 的 ios::sync_with_stdio(false) 和 cin.tie(nullptr)，Python 的 sys.stdin.buffer 等）以提高效率。

标签：排序，模板

题解