【模板】排序

思路

拿到这题，题意很直白：给你一个整数数组，按从小到大排好序输出就行。

那问题来了——排序算法那么多，这里该用哪个？

对于竞赛和实际工程来说，直接用标准库的排序就是最优选择。C++ 的 sort() 底层是 IntroSort（快排 + 堆排 + 插入排序的混合体），Java 的 Arrays.sort() 对基本类型用的是双轴快排。两者平均时间复杂度都是 ，而且经过了大量优化，手写很难比它们更快。

唯一要注意的就是 I/O 效率。数据量大的时候，C++ 用 scanf/printf 比 cin/cout 快不少；Java 用 BufferedReader + StringBuilder 比 Scanner 快很多。这是竞赛中的常规操作。

代码

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int* a = new int[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a + n);
    for (int i = 0; i < n; i++) {
        if (i) putchar(' ');
        printf("%d", a[i]);
    }
    putchar('\n');
    delete[] a;
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(a);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i > 0) sb.append(' ');
            sb.append(a[i]);
        }
        System.out.println(sb);
    }
}

import sys
input = sys.stdin.readline

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

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = lines[1].split(' ').map(Number);
    a.sort((x, y) => x - y);
    console.log(a.join(' '));
});

复杂度分析

  • 时间复杂度: ，标准库排序的平均复杂度。
  • 空间复杂度: ，存储数组本身。排序过程中额外空间 （递归栈）。

小结

排序是最基础的算法模板，没什么弯弯绕绕。竞赛中几乎不会手写排序，直接调库就对了。这题真正考的其实是两点：一是你会不会用语言自带的排序函数，二是 I/O 能不能写利索。C++ 记住 sort(a, a+n) 配合 scanf/printf，Java 记住 Arrays.sort() 配合 BufferedReader，这套模板后面会反复用到。