5.2.3. 结构体 Vector 排序

问题：

你想对结构体类型的动态数组 vector 进行排序。

解决方案：

依据自然顺序（按名称和年龄），对具有 name 和 age 属性的 Person 结构体 Vector 排序。为了使 Person 可排序，你需要四个 traits：Eq、PartialEq、Ord，以及 PartialOrd。这些 traits 可以被简单地派生。你也可以使用 vec:sort_by 方法自定义比较函数，仅按照年龄排序。

以下实例代码引用自开源书籍项目《Cookin’ with Rust》，笔者在其基础上稍作修改。

#[derive(Debug, Eq, Ord, PartialEq, PartialOrd)]
struct Person {
    name: String,
    age: u32
}

impl Person {
    pub fn new(name: &str, age: u32) -> Self {
        Person {
            name: name.to_string(),
            age
        }
    }
}

fn main() {
    let mut people = vec![
        Person::new("Zhang", 25),
        Person::new("Liu", 60),
        Person::new("Wang", 1),
    ];
    println!("  排序前： {:?}", people);

    // 根据获得的自然顺序（name 和 age）对 people 进行排序
    people.sort();
    println!("  排序后（name 和 age）： {:?}", people);

    assert_eq!(
        people,
        vec![
            Person::new("Liu", 60),
            Person::new("Wang", 1),
            Person::new("Zhang", 25),
        ]);

    // 根据 age 值对 people 进行排序
    people.sort_by(|a, b| b.age.cmp(&a.age));
    println!("  排序后（age）： {:?}", people);

    assert_eq!(
        people,
        vec![
            Person::new("Liu", 60),
            Person::new("Zhang", 25),
            Person::new("Wang", 1),
        ]);

}

代码第 1-5 行，创建结构体类型 Person，并为其派生一系列宏 Debug, Eq, Ord, PartialEq, PartialOrd。

代码第 14 行，为结构体类型 Person 实现 new 方法。并且在代码第 17-21 行，使用 new 方法绑定值到结构体 people。

代码第 25 行，根据自然顺序，即为全部值 name 和 age，对结构体 people 进行排序。

代码第 37 行，仅根据 age 值对结构体 people 进行排序，在 sort_by 方法中通过闭包，指定排序依据 age 值。

构建并运行后，结果大抵如下所示。

  排序前： [Person { name: "Zhang", age: 25 }, Person { name: "Liu", age: 60 }, Person { name: "Wang", age: 1 }]
  排序后（name 和 age）： [Person { name: "Liu", age: 60 }, Person { name: "Wang", age: 1 }, Person { name: "Zhang", age: 25 }]
  排序后（age）： [Person { name: "Liu", age: 60 }, Person { name: "Zhang", age: 25 }, Person { name: "Wang", age: 1 }]

断言的使用和整型 vector 排序类似，不再赘述。

讨论：

Eq 是对等式进行等价关系比较的 trait。这意味着，除了 a == b 和 a != b 严格可逆比较外，等式必须为（对于所有 a、b 和 c 而言）：

• 自反：a == a；
• 对称：a == b 意味着 b == a；以及
• 等量代换：a == b 和 b == c 意味着 a == c。

PartialEq 是对等式部分进行等价关系比较的 trait。对于没有完全等价关系的类型，实现此 trait 允许部分相等。例如，在浮点数中，NaN != NaN，所以浮点类型实现 PartialEq 而不是 Eq。从形式上讲，等式必须为（对于所有 a、b 和 c 而言）：

• 对称：a == b 意味着 b == a；以及
• 等量代换：a == b 和 b == c 意味着 a == c。

Ord 是用于构成全序关系类型的 trait。如果是全序关系的排序（对于所有 a、b 和 c 而言）：

• 完全非对称：a < b，a == b 或 a > b 中的一个为真；以及
• 等量代换：a < b 和 b < c 意味着 a < c。对于 == 和 >，同样具有等量代换关系。

PartialOrd 是可比较排序规则的 trait。对于所有 a、b 和 c 而言，比较关系必须满足：

• 非对称：如果 a < b，那么 !(a > b)，以及 a > b 意味着 !(a < b)；以及
• 等量代换：a < b 和 b < c 意味着 a < c。对于 == 和 >，同样具有等量代换关系。

还有 vec::sort，其对切片进行排序，这种排序是稳定的（即不重新排序相等的元素）。在合适的场景，不稳定排序是首选的，因为它通常比稳定排序快，并且不分配辅助内存。