进阶 · 17

排序

从小到大、从大到小，或按自己定的规则排列。

排序就是把值按顺序排好。
下面的示例把数字从小到大、从大到小排列，再把单词按字母顺序和“短的在前”排列。

nums = list(map(int, input().split()))words = input().split()print(*sorted(nums))print(*sorted(nums, reverse=True))print(*sorted(words))print(*sorted(words, key=lambda w: (len(w), w)))

const [line1, line2] = require("fs").readFileSync(0, "utf8").trim().split("\n");const nums = line1.trim().split(/\s+/).map(Number);const words = line2.trim().split(/\s+/);console.log([...nums].sort((a, b) => a - b).join(" "));console.log([...nums].sort((a, b) => b - a).join(" "));console.log([...words].sort().join(" "));const byLength = (a, b) => a.length - b.length || (a < b ? -1 : a > b ? 1 : 0);console.log([...words].sort(byLength).join(" "));

import { readFileSync } from "node:fs";const [line1, line2]: string[] = readFileSync(0, "utf8").trim().split("\n");const nums: number[] = line1.trim().split(/\s+/).map(Number);const words: string[] = line2.trim().split(/\s+/);console.log([...nums].sort((a, b) => a - b).join(" "));console.log([...nums].sort((a, b) => b - a).join(" "));console.log([...words].sort().join(" "));const byLength = (a: string, b: string): number => a.length - b.length || (a < b ? -1 : a > b ? 1 : 0);console.log([...words].sort(byLength).join(" "));

import java.util.*;import java.util.stream.*; public class Main {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int[] nums = Arrays.stream(sc.nextLine().trim().split("\\s+")).mapToInt(Integer::parseInt).toArray();        String[] words = sc.nextLine().trim().split("\\s+");        Arrays.sort(nums);        System.out.println(Arrays.stream(nums).mapToObj(String::valueOf).collect(Collectors.joining(" ")));        Integer[] boxed = Arrays.stream(nums).boxed().toArray(Integer[]::new);        Arrays.sort(boxed, Comparator.reverseOrder());        System.out.println(Arrays.stream(boxed).map(String::valueOf).collect(Collectors.joining(" ")));        String[] abc = words.clone();        Arrays.sort(abc);        System.out.println(String.join(" ", abc));        Arrays.sort(words, Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));        System.out.println(String.join(" ", words));    }}

using System;using System.Linq; class Program{    static void Main()    {        int[] nums = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();        string[] words = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);        Array.Sort(nums);        Console.WriteLine(string.Join(" ", nums));        Console.WriteLine(string.Join(" ", nums.OrderByDescending(x => x)));        Console.WriteLine(string.Join(" ", words.OrderBy(w => w, StringComparer.Ordinal)));        var byLength = words.OrderBy(w => w.Length).ThenBy(w => w, StringComparer.Ordinal);        Console.WriteLine(string.Join(" ", byLength));    }}

#include <algorithm>#include <functional>#include <iostream>#include <sstream>#include <string>#include <vector> template <typename T>void print(const std::vector<T>& v) {    for (size_t i = 0; i < v.size(); i++) std::cout << (i > 0 ? " " : "") << v[i];    std::cout << '\n';} int main() {    std::string line;    std::getline(std::cin, line);    std::istringstream in1(line);    std::vector<int> nums;    for (int x; in1 >> x;) nums.push_back(x);    std::getline(std::cin, line);    std::istringstream in2(line);    std::vector<std::string> words;    for (std::string w; in2 >> w;) words.push_back(w);     std::sort(nums.begin(), nums.end());    print(nums);    std::sort(nums.begin(), nums.end(), std::greater<int>());    print(nums);    std::sort(words.begin(), words.end());    print(words);    std::sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) {        if (a.size() != b.size()) return a.size() < b.size();        return a < b;    });    print(words);}

#include <stdio.h>#include <stdlib.h>#include <string.h> int asc(const void *a, const void *b) {    int x = *(const int *)a, y = *(const int *)b;    return (x > y) - (x < y);}int desc(const void *a, const void *b) { return asc(b, a); }int abc(const void *a, const void *b) { return strcmp(*(char *const *)a, *(char *const *)b); }int by_length(const void *a, const void *b) {    const char *s = *(char *const *)a, *t = *(char *const *)b;    size_t ls = strlen(s), lt = strlen(t);    if (ls != lt) return ls < lt ? -1 : 1;    return strcmp(s, t);} int main(void) {    char line[4096], wline[4096], *words[1000];    int nums[1000], n = 0, m = 0;    fgets(line, sizeof line, stdin);    fgets(wline, sizeof wline, stdin);    for (char *p = strtok(line, " \r\n"); p; p = strtok(NULL, " \r\n")) nums[n++] = atoi(p);    for (char *p = strtok(wline, " \r\n"); p; p = strtok(NULL, " \r\n")) words[m++] = p;     qsort(nums, n, sizeof nums[0], asc);    for (int i = 0; i < n; i++) printf(i > 0 ? " %d" : "%d", nums[i]);    printf("\n");    qsort(nums, n, sizeof nums[0], desc);    for (int i = 0; i < n; i++) printf(i > 0 ? " %d" : "%d", nums[i]);    printf("\n");    qsort(words, m, sizeof words[0], abc);    for (int i = 0; i < m; i++) printf(i > 0 ? " %s" : "%s", words[i]);    printf("\n");    qsort(words, m, sizeof words[0], by_length);    for (int i = 0; i < m; i++) printf(i > 0 ? " %s" : "%s", words[i]);    printf("\n");    return 0;}

nums = 控制台.读数字();words = 控制台.读行().分割(); // 앞이 먼저면 음수, 뒤가 먼저면 양수큰것먼저(앞, 뒤){    返回 뒤 - 앞;} 짧은것먼저(앞, 뒤){    如果 (앞.长度 != 뒤.长度)    {        返回 앞.长度 - 뒤.长度;    }    如果 (앞 < 뒤)    {        返回 -1;    }    如果 (앞 > 뒤)    {        返回 1;    }    返回 0;} nums.排序();控制台.输出(nums);nums.排序(큰것먼저);控制台.输出(nums);words.排序();控制台.输出(words);words.排序(짧은것먼저);控制台.输出(words);

stdin

10 9 1 25 3
pear fig banana kiwi apple

stdout

1 3 9 10 25
25 10 9 3 1
apple banana fig kiwi pear
fig kiwi pear apple banana

要点

默认情况下，数字按大小，字符串按字典序（字符编码顺序）。
有的排序返回新列表，有的原地修改。
Python 的 sorted(nums) 返回新列表，nums.sort() 原地排序。
给出规则有两种方式。
键函数说明每个值拿什么来比（Python 的 key=lambda w: (len(w), w) 表示“按长度，相同再按字母”）。
比较函数接收两个值：前者在先返回负数，相同返回 0，后者在先返回正数。
稳定排序会让规则相同的值保持原来的先后顺序。
用不稳定的排序时，要把相同时的规则（长度相同按字母）也写进比较函数。

各语言的写法

Python	`sorted(nums)`（新列表）、`nums.sort()`（原地）。从大到小用 `reverse=True`，规则用 `key=lambda w: (len(w), w)`。稳定
JavaScript	`arr.sort((a, b) => a - b)` — 原地排序。不传比较函数时，数字也按字符串比较。多个规则写成 `a.length - b.length \|\| ...`。 ES2019 起稳定
TypeScript	和 JavaScript 一样
Java	`Arrays.sort`、`Collections.sort`。从大到小用 `Comparator.reverseOrder()`，规则用 `Comparator.comparingInt(String::length).thenComparing(...)`。对象数组和 `Collections.sort` 是稳定的。 `int[]` 不接受比较器
C#	`Array.Sort`、`List.Sort`（原地，不保证稳定），LINQ `OrderBy(...).ThenBy(...)`、`OrderByDescending`（稳定）
C++	`std::sort(v.begin(), v.end())`，从大到小用 `std::greater<int>()`。比较 lambda 返回 `bool`，表示“前者是否在先”。需要稳定时用 `std::stable_sort`
C	`qsort(a, n, sizeof a[0], cmp)` — `cmp` 接收两个指针，返回负数、0 或正数。不保证稳定
Craykon	`列表.排序()` 从小到大。像 `列表.排序(短的在前)` 这样传入比较函数名。稳定

常见错误

数字不传比较函数就 `sort()`JavaScript · TypeScript

console.log([10, 9, 1].sort());

→ [ 1, 10, 9 ] — 数字被转成字符串来比较

数字一定要传 (a, b) => a - b。

写成了 `nums = nums.sort()`Python

nums = [3, 1, 2]
nums = nums.sort()
print(nums)

→ None — sort 原地排序，不返回任何东西

只写 nums.sort()，或者写 nums = sorted(nums)。

给 `int[]` 传了比较器Java

int[] a = {3, 1, 2};
Arrays.sort(a, Comparator.reverseOrder());

→ 编译错误 — int[] 版的 sort 不接受比较器

像示例那样转成 Integer[]，或者从小到大排好后倒着读。

各语言的差异
把 C qsort 的比较函数写成 return a - b;，在大负数减大正数时（例如 -2000000000 - 2000000000）int 会溢出，符号翻转，顺序就错了。
请用比较来写：(a > b) - (a < b)。

排序

要点

各语言的写法

常见错误

数字不传比较函数就 sort()JavaScript · TypeScript

写成了 nums = nums.sort()Python

给 int[] 传了比较器Java

练习题

数字不传比较函数就 `sort()`JavaScript · TypeScript

写成了 `nums = nums.sort()`Python

给 `int[]` 传了比较器Java