Rust 排序与查找

排序和查找几乎是每个程序都要做的事：按分数给玩家排名、按名字列出文件、找出最便宜的商品。Rust 给 vector 和 slice 内置了一整套排序和查找方法，所以你很少需要自己写算法。

这些方法大多接收一个闭包，用来说明怎样比较两个元素。只要习惯了这一个思路，这一页剩下的内容都只是它的变化。

sort 和 sort_unstable

.sort() 把元素按升序排列（从小到大）。它就地修改 vector，所以 vector 必须是 mut 的。数字按大小排序，字符串按字母顺序排序。

fn main() {
    let mut scores = vec![42, 7, 99, 7, 15];
    scores.sort();
    println!("{:?}", scores);

    let mut names = vec!["Zoe", "adam", "Bob", "Ana"];
    names.sort_unstable();
    println!("{:?}", names);
}

输出：

[7, 7, 15, 42, 99]
["Ana", "Bob", "Zoe", "adam"]

▶ 动手试一试

有两点值得注意：

• "adam" 排在最后。字符串按字符编码比较，所有大写字母都排在所有小写字母前面。如果你想要“字典”顺序，就按 name.to_lowercase() 排序（下面有示例）。
• sort_unstable 通常稍快一点，而且不占用额外内存。“不稳定”（unstable）并不是说它有 bug，而是指比较结果相等的元素可能会交换位置。对普通的数字或字符串来说，你根本看不出区别，所以把它当默认选择没问题。

倒序排列

从大到小排序，常见的写法有三种。在这里它们的结果完全一样。

use std::cmp::Reverse;

fn main() {
    let mut a = vec![3, 8, 1, 5];
    a.sort();
    a.reverse();
    println!("{:?}", a);

    let mut b = vec![3, 8, 1, 5];
    b.sort_by(|x, y| y.cmp(x)); // y 在 x 前面 = 降序
    println!("{:?}", b);

    let mut c = vec![3, 8, 1, 5];
    c.sort_by_key(|&n| Reverse(n));
    println!("{:?}", c);
}

输出：

[8, 5, 3, 1]
[8, 5, 3, 1]
[8, 5, 3, 1]

▶ 动手试一试

x.cmp(y) 返回一个 Ordering：Less、Equal 或 Greater。sort_by 用它来决定哪个元素排在前面。写成 y.cmp(x) 会把每一次判断都反过来，整个顺序也就反过来了。Reverse 是 std::cmp 里的一个小包装类型，对排序键做同样的反转。

浮点数排序

试着对一个 f64 的 vector 调用 .sort()，Rust 会拒绝：

fn main() {
    let mut prices = vec![2.5, 0.99, 10.0];
    prices.sort();
}

error[E0277]: the trait bound `{float}: Ord` is not satisfied
 --> src/main.rs:3:12
  |
3 |     prices.sort();
  |            ^^^^ the trait `Ord` is not implemented for `{float}`

编译器说的是：浮点数（{float}）没有实现 Ord trait。为什么？.sort() 需要全序（total order，也就是 Ord trait）：任意两个值之间，必须是小于、等于或大于其中之一。浮点数有一个特殊值 NaN（“not a number”，不是数字），它既不小于、不等于、也不大于任何值，连它自己也不例外。所以浮点数只实现了 PartialOrd，而 .partial_cmp() 返回的是 Option<Ordering>，遇到 NaN 时就是 None。

有两种好的修复方法：

fn main() {
    let mut prices = vec![2.5, 0.99, 10.0, 4.75];

    // 如果你确定里面没有 NaN：
    prices.sort_by(|a, b| a.partial_cmp(b).unwrap());
    println!("{:?}", prices);

    // 有 NaN 也能用（NaN 会排到最后）：
    let mut readings = vec![3.2, f64::NAN, -1.0, 0.5];
    readings.sort_by(|a, b| a.total_cmp(b));
    println!("{:?}", readings);
}

输出：

[0.99, 2.5, 4.75, 10.0]
[-1.0, 0.5, 3.2, NaN]

▶ 动手试一试

partial_cmp(...).unwrap() 一碰到 NaN 就会 panic。total_cmp 永远不会 panic，因为它给每个浮点数（包括 NaN）都规定了一个固定的位置。除非有特别的理由，否则优先用 total_cmp。

sort_by_key 和结构体排序

sort_by_key 接收一个闭包，用来挑出按什么排序。这特别适合结构体：你选一个字段就行。

#[derive(Debug)]
struct Product {
    name: String,
    price_cents: u32,
}

fn main() {
    let mut items = vec![
        Product { name: String::from("pen"), price_cents: 150 },
        Product { name: String::from("Notebook"), price_cents: 499 },
        Product { name: String::from("eraser"), price_cents: 75 },
    ];

    items.sort_by_key(|p| p.price_cents);
    for p in &items {
        println!("{} - {}", p.price_cents, p.name);
    }

    items.sort_by_key(|p| p.name.to_lowercase());
    let names: Vec<&str> = items.iter().map(|p| p.name.as_str()).collect();
    println!("{:?}", names);
}

输出：

75 - eraser
150 - pen
499 - Notebook
["eraser", "Notebook", "pen"]

▶ 动手试一试

商品名（钢笔、笔记本、橡皮）保留了英文：这个例子要演示按字母排序时大小写的影响，中文名就看不出来了。

键闭包必须返回一个拥有所有权的值。p.price_cents 是 u32，会被复制，所以没问题。如果是 String 字段，你就需要一个新的 String，这就是第二次排序用 to_lowercase() 的原因：它会创建一个新字符串。（见下面的常见误区。）

按多个字段排序

一个经典任务：把学生按成绩排序，高分在前；成绩相同的，再按名字 A 到 Z 排。用 sort_by 加上 .then_with()，只有第一次比较打平时，它才会去看第二次比较。

struct Student {
    name: String,
    grade: u32,
}

fn main() {
    let mut class = vec![
        Student { name: String::from("Liam"), grade: 88 },
        Student { name: String::from("Ava"), grade: 95 },
        Student { name: String::from("Noah"), grade: 88 },
        Student { name: String::from("Emma"), grade: 88 },
        Student { name: String::from("Mia"), grade: 72 },
    ];

    class.sort_by(|a, b| {
        b.grade.cmp(&a.grade)               // 成绩：从高到低
            .then_with(|| a.name.cmp(&b.name)) // 然后名字：A 到 Z
    });

    for s in &class {
        println!("{:>3}  {}", s.grade, s.name);
    }
}

输出：

 95  Ava
 88  Emma
 88  Liam
 88  Noah
 72  Mia

▶ 动手试一试

还有个更短的写法：返回一个元组作为排序键。元组先比较第一个元素，再比较第二个，依此类推：

class.sort_by_key(|s| (Reverse(s.grade), s.name.clone()));

得到的顺序完全一样。写起来很整洁，但它会克隆每一个名字，所以对大列表来说，sort_by 加 then_with 是更好的习惯。

用 dedup 去重

.dedup() 会删除和紧挨在它前面的元素相等的元素。所以只有先排好序，它才能删掉所有重复项。

fn main() {
    let mut tags = vec!["rust", "web", "rust", "cli", "web", "web"];

    let mut not_sorted = tags.clone();
    not_sorted.dedup();
    println!("dedup only:   {:?}", not_sorted);

    tags.sort();
    tags.dedup();
    println!("sort + dedup: {:?}", tags);
}

输出：

dedup only:   ["rust", "web", "rust", "cli", "web"]
sort + dedup: ["cli", "rust", "web"]

▶ 动手试一试

这里的标签（dedup only＝只去重，sort + dedup＝先排序再去重）保留了英文，因为它们靠空格对齐，换成中文会错位。

第一次尝试里，只有挨在一起的两个 "web" 被合并了。所以要先排序，再去重。如果你需要保留原来的顺序，可以用 HashSet 那一页介绍的 HashSet 技巧。

查找：contains、position、max、min、binary_search

下面是最常用的查找工具：

• contains(&x)：在不在里面？返回 bool。
• iter().position(...)：第一个匹配项在哪儿？返回 Option<usize>。
• iter().max() / iter().min()：最大值和最小值，以 Option 返回（列表为空时是 None）。
• iter().max_by_key(...) / min_by_key(...)：按某个字段找最大或最小的元素。
• binary_search(&x)：非常快的查找，但只能用在排好序的列表上。找到时返回 Ok(index)，找不到时返回 Err(index)，告诉你它应该放在哪儿。

fn main() {
    let temps = vec![18, 25, 12, 31, 25];
    println!("有 31 吗？{}", temps.contains(&31));
    println!("第一个高于 20 的位置：{:?}", temps.iter().position(|&t| t > 20));
    println!("最大：{:?}，最小：{:?}", temps.iter().max(), temps.iter().min());

    let players = vec![("ana", 340), ("ben", 515), ("chen", 220)];
    let best = players.iter().max_by_key(|(_, score)| *score).unwrap();
    println!("第一名：{}", best.0);

    let mut sorted = vec![10, 20, 30, 40];
    println!("{:?}", sorted.binary_search(&30));
    let missing = sorted.binary_search(&25);
    println!("{:?}", missing);
    if let Err(pos) = missing {
        sorted.insert(pos, 25); // 列表依然保持有序
    }
    println!("{:?}", sorted);
}

输出：

有 31 吗？true
第一个高于 20 的位置：Some(1)
最大：Some(31)，最小：Some(12)
第一名：ben
Ok(2)
Err(2)
[10, 20, 25, 30, 40]

▶ 动手试一试

binary_search 先检查中间的元素，扔掉不可能包含目标值的那一半，然后重复这个过程。在一百万个元素的列表里，大约只需要 20 次检查，而不是最多一百万次。Err(pos) 这个结果也很好用：在 pos 处插入，列表依然有序。

警告

max() 和 min() 需要 Ord，所以它们同样不能用在浮点数上。改用 max_by(|a, b| a.total_cmp(b))，和排序时的修复方法一样。

常见误区

在 sort_by_key 里返回借来的 String 字段。 这样写看起来很自然，却编译不过：

students.sort_by_key(|s| s.name);

error[E0507]: cannot move out of `s.name` which is behind a shared reference
  --> src/main.rs:12:30
   |
12 |     students.sort_by_key(|s| s.name);
   |                              ^^^^^^ move occurs because `s.name` has type `String`, which does not implement the `Copy` trait

编译器说：s.name 在共享引用后面，不能把它移出来。闭包只是借用每个学生，所以没法把 String 交出去。要么克隆它（|s| s.name.clone()），要么干脆用 sort_by(|a, b| a.name.cmp(&b.name))，完全避免复制。

在没排序的列表上用 binary_search。 它不会崩溃，但结果毫无意义：值明明就在那儿，它却可能说找不到。一定要先排序，或者改用 contains / position。

练习

1. 排行榜

玩家以 (name, score) 元组表示：("ben", 70)、("ana", 95)、("chen", 70)、("dev", 88)、("eli", 60)。按分数从高到低排序，分数相同的按名字 A 到 Z 排。只打印前三名。提示：用 sort_by 加 .then_with()，前三名用 slice &players[..3] 取出。

查看答案

fn main() {
    let mut players = vec![("ben", 70), ("ana", 95), ("chen", 70), ("dev", 88), ("eli", 60)];

    players.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)));

    for (name, score) in &players[..3] {
        println!("{score} {name}");
    }
}

输出：

95 ana
88 dev
70 ben

▶ 动手试一试

对元组来说，.0 是名字，.1 是分数。ben 和 chen 都是 70 分，于是由名字打破平局，ben 挤进了前三名。

2. 价格的中位数

找出价格 3.5, 1.25, 9.0, 4.75, 2.0 的中位数（排在正中间的值）。打印排好序的列表和中位数。提示：用 total_cmp 排序；长度为奇数的列表，中间元素的索引是 len() / 2。

查看答案

fn main() {
    let mut prices: Vec<f64> = vec![3.5, 1.25, 9.0, 4.75, 2.0];

    prices.sort_by(|a, b| a.total_cmp(b));
    let median = prices[prices.len() / 2];

    println!("排序后：{:?}", prices);
    println!("中位数：{median}");
}

输出：

排序后：[1.25, 2.0, 3.5, 4.75, 9.0]
中位数：3.5

▶ 动手试一试

Vec<f64> 这个类型注解很重要。没有它，Rust 执行到 total_cmp 时还不知道这些数字是哪种浮点类型，就会报错“no method named total_cmp”（找不到名为 total_cmp 的方法），拒绝编译。

总结

• sort() 和 sort_unstable() 就地排序，从小到大。想从大到小，就用 reverse()、y.cmp(x) 或 Reverse。
• 因为有 NaN，浮点数不能用 sort()。改用 sort_by(|a, b| a.total_cmp(b))。
• sort_by_key 按选定的字段排序；sort_by 加 .then_with() 可以按多个字段排序。
• dedup() 只删除相邻的相等元素，所以要先排序。
• contains、position、max/min 和 max_by_key 能在任何列表里查找；binary_search 快得多，但需要列表已经排好序。

小测验

小测验

1. 为什么 vec![1.5, 0.5].sort() 编译不过？

浮点数不能存进 Vec sort 只能用于字符串 浮点数没有实现 Ord，因为 NaN 无法比较 这个 vector 不是 mut 的

2. vec![1, 1, 2, 1].dedup() 之后，vector 里剩下什么？

[1, 2] [1, 2, 1] [2] [1, 1, 2, 1]

3. vec![10, 20, 30].binary_search(&25) 返回什么？

Err(2) Ok(2) None -1

4. 在 a.grade.cmp(&b.grade).then_with(|| a.name.cmp(&b.name)) 里，什么时候才会比较名字？

总是会，而且在比较成绩之前 永远不会 只在名字不同的时候 只在两个成绩相等的时候

得分: 0 / 4

延伸阅读

• Slice 方法：sort、sort_by、binary_search 等 — 标准库文档（英文）：所有排序和查找方法，附有速度和稳定性的说明。
• std::cmp::Ordering — 标准库文档（英文）：Less、Equal、Greater，以及 then、then_with 和 reverse。
• std::cmp::Reverse — 标准库文档（英文）：让排序键从大到小排列的包装类型。
• f64::total_cmp — 标准库文档（英文）：给浮点数排序时，NaN、负零和无穷大究竟会排在哪里。
• Sort a Vector — Rust Cookbook（英文）：给整数、浮点数和结构体排序的简短示例。