{ }codelper

学习 › C++

进阶 · 17

排序

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

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

#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);}
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，后者在先返回正数。
  • 稳定排序会让规则相同的值保持原来的先后顺序。
    用不稳定的排序时，要把相同时的规则（长度相同按字母）也写进比较函数。

各语言的写法

Pythonsorted(nums)（新列表）、nums.sort()（原地）。
从大到小用 reverse=True，规则用 key=lambda w: (len(w), w)。
稳定
JavaScriptarr.sort((a, b) => a - b) — 原地排序。
不传比较函数时，数字也按字符串比较。
多个规则写成 a.length - b.length || ...。
ES2019 起稳定
TypeScript和 JavaScript 一样
JavaArrays.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
Cqsort(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)。

练习题

  1. 数字排序8P0036
  2. 单词频率排名8P0034
  3. 整理招牌字块8P0253
  4. 数值顺序和字典顺序8P0320
  5. 生日先到的朋友排在前面8P0376
  6. 成绩排名表8P0067
  7. 一间会议室安排最多会议8P0090
  8. 并集、交集、差集8P0099