题解 | #【模板】排序#

题目链接

BGN20 【模板】排序

题目描述

给定一个长度为 $N$ 的整数数组 $A$ （允许元素重复），请将其按非递减顺序排序并输出。

输入描述

第一行输入整数 $N$ ，表示数组长度。第二行输入 $N$ 个整数 $a_i$ 。

输出描述

在一行上输出排序后的数组，各元素以空格分隔。

样例

输入

5
5 4 3 2 1

输出

1 2 3 4 5

解题思路

本题是排序算法的模板题，要求对一个整数数组进行非递减排序。

最直接、高效且在竞赛中常用的方法是利用各编程语言标准库中内置的排序函数。这些函数通常经过了高度优化（例如，C++的 std::sort 通常是内省排序，Java的 Arrays.sort 对基本类型是双轴快排，Python的 sort 是Timsort），能够稳定、快速地完成排序任务。

C++: 使用 <algorithm> 头文件中的 std::sort 函数。
Java: 使用 java.util.Arrays 类中的 sort 方法。
Python: 使用列表对象的 sort() 方法或内置的 sorted() 函数。

算法步骤如下：

读入数组的长度 $N$ 。
读入 $N$ 个整数并存储在一个数组或动态数组（如 C++ 的 vector）中。
调用对应语言的内置排序函数对数组进行排序。
遍历排序后的数组，按格式要求输出所有元素，元素间用空格隔开。

代码

c++
java
python

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

using namespace std;

int main() {
    int n;
    cin >> n;
    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] << (i == n - 1 ? "" : " ");
    }
    cout << '\n';

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        Arrays.sort(a);

        for (int i = 0; i < n; i++) {
            System.out.print(a[i] + (i == n - 1 ? "" : " "));
        }
        System.out.println();
    }
}

# -*- coding: utf-8 -*-

n = int(input())
a = list(map(int, input().split()))

a.sort()

print(*a)

算法及复杂度

算法：标准库排序
时间复杂度： $O(N \cdot \log N)$ ，其中 $N$ 是数组的长度。这是基于比较的排序算法的平均和最优时间复杂度。
空间复杂度： $O(N)$ ，主要用于存储输入的数组。标准库排序函数本身可能会使用 $O(\log N)$ （如快速排序的递归栈）或 $O(N)$ （如归并排序）的额外空间。