题解 | #【模板】排序#

题目链接

题目描述

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

解题思路

这是一个基础的排序问题。最直接、高效的方法是利用各编程语言标准库中提供的内置排序函数。这些函数通常都经过了高度优化（例如，C++的std::sort通常是内省排序，Java是双轴快速排序，Python是Timsort），能够稳定、快速地处理各种数据。

基本步骤：

读取整数 $N$ 和数组元素。
调用对应语言的排序函数对数组进行原地排序。
遍历排序后的数组，并按指定格式输出。

这种方法代码简洁，不易出错，并且性能优于大部分手动实现的简单排序算法（如冒泡排序或选择排序）。

代码

cpp
java
python

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

using namespace std;

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

    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    sort(arr.begin(), arr.end());

    for (int i = 0; i < n; ++i) {
        cout << arr[i] << (i == n - 1 ? "" : " ");
    }
    cout << endl;

    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[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr);

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

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

arr.sort()

# 使用*解包操作符，可以方便地输出列表，并用空格分隔
print(*arr)

算法及复杂度

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