Vector 排序

应用场景

本节主要内容是对 Rust 语言中的 Vec 类型进行排序。Vec 类型也被称为 vector,它是动态数组。

vector 允许我们在一个单独的数据结构中储存多于一个的值,它在内存中彼此相邻地排列所有的值。vector 只能储存相同类型的值,但其存储类型可以自定义。

vector 排序在拥有一系列项的场景下非常实用,例如文件中的文本行,或是购物车中商品的价格等。

crate 介绍

std(The Rust Standard Library)

Rust 标准库是可移植的 Rust 软件的基础,它针对广泛的 Rust 生态系统,是其最核心的一组共享抽象,经过严格的测试和检验。

Rust 标准库提供了核心类型,如 Vec<T>Option<T>、语言原语上的库定义操作、标准宏、I/O,以及多线程等。

std 默认适用于所有 Rust crate。因此,可以通过 std 路径,在 use 语句中访问标准库,就像 use std::env 一样。

实例实践

整数 Vector 排序

std-badge cat-science-badge

这个实例通过 vec::sort 对一个整数 Vector 进行排序。另一种方法是使用 vec::sort_unstable,后者运行速度更快一些,但不保持相等元素的顺序。

  • vec::sort:对切片进行排序,这种排序是稳定的(即不重新排序相等的元素)。在合适的场景,不稳定排序是首选的,因为它通常比稳定排序快,并且不分配辅助内存。
  • vec::sort_unstable:对切片进行排序,但可能不会保留相等元素的顺序。这种排序类型不甚稳定(即,可能重新排序相等的元素)。

以下实例代码引用自 rust-cookbook 项目,笔者在其基础上稍作修改。

fn main() {
    let mut vec = vec![1, 5, 10, 2, 15];
    println!("  排序前: {:?}", vec);

    vec.sort();
    println!("  排序后: {:?}", vec);

    assert_eq!(vec, vec![1, 2, 5, 10, 15]);
}

代码第 5 行,通过 sort 方法对 vector 进行排序。

构建并运行后,结果大抵如图 3.2-1 所示。

sort

图 3.2-1

注意:第 8 行是两个 vector 比较的断言,如果不相等,会输出 “thread ‘main’ panicked at ‘assertion failed: (left == right)”,请你自行尝试。

浮点数 Vector 排序

std-badge cat-science-badge

f32 或 f64 的 vector,可以使用 vec::sort_byPartialOrd::partial_cmp 对其进行排序。

  • vec::sort_by:使用比较器(comparator )函数对切片进行排序,这种排序是稳定的(即不重新排序相等的元素)。比较器(comparator )函数必须为切片中的元素定义一个总顺序。如果不是全序关系排序,则不指定元素的顺序。如果排序是全序关系(对于所有 abc),则:
    • 完全反对称:a < ba == ba > b 中的一个为真,并且
    • 等量代换:a < bb < c 意味着 a < c。对于 ==>,同样具有等量代换关系。
  • PartialOrd::partial_cmp:如果存在其它值(other ),此方法将返回自己(self)其它值(other )之间的排序。

以下实例代码引用自 rust-cookbook 项目,笔者在其基础上稍作修改。

fn main() {
    let mut vec = vec![1.1, 1.15, 5.5, 1.123, 2.0];
    println!("  排序前: {:?}", vec);

    vec.sort_by(|a, b| a.partial_cmp(b).unwrap());
    println!("  排序后: {:?}", vec);

    assert_eq!(vec, vec![1.1, 1.123, 1.15, 2.0, 5.5]);
}

代码第 5 行,使用 PartialOrd::partial_cmp 对浮点型 vector 进行排序。

构建并运行后,结果大抵如图 3.2-2 所示。

sort-float

图 3.2-2

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

结构体 Vector 排序

std-badge cat-science-badge

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

  • Eq:对等式进行等价关系比较的 trait。这意味着,除了 a == ba != b 严格可逆比较外,等式必须为(对于所有 abc 而言):
    • 自反:a == a
    • 对称:a == b 意味着 b == a;以及
    • 等量代换:a == bb == c 意味着 a == c
  • PartialEq:对等式部分进行等价关系比较的 trait。对于没有完全等价关系的类型,实现此 trait 允许部分相等。例如,在浮点数中,NaN != NaN,所以浮点类型实现 PartialEq 而不是 Eq。从形式上讲,等式必须为(对于所有 abc 而言):
    • 对称:a == b 意味着 b == a;以及
    • 等量代换:a == bb == c 意味着 a == c
  • Ord:用于构成全序关系类型的 trait。如果是全序关系的排序(对于所有 abc 而言):
    • 完全非对称:a < ba == ba > b 中的一个为真;以及
    • 等量代换:a < bb < c 意味着 a < c。对于 ==>,同样具有等量代换关系。
  • PartialOrd:可比较排序规则的 trait。对于所有 abc 而言,比较关系必须满足:
    • 非对称:如果 a < b,那么 !(a > b),以及 a > b 意味着 !(a < b);以及
    • 等量代换:a < bb < c 意味着 a < c。对于 ==>,同样具有等量代换关系。
  • vec::sort:对切片进行排序,这种排序是稳定的(即不重新排序相等的元素)。在合适的场景,不稳定排序是首选的,因为它通常比稳定排序快,并且不分配辅助内存。

以下实例代码引用自 rust-cookbook 项目,笔者在其基础上稍作修改。

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

impl Person {
    pub fn new(name: String, age: u32) -> Self {
        Person {
            name,
            age
        }
    }
}

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

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

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

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

    assert_eq!(
        people,
        vec![
            Person::new("Liu".to_string(), 60),
            Person::new("Zhang".to_string(), 25),
            Person::new("Wang".to_string(), 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 值。

构建并运行后,结果大抵如图 3.2-3 所示。

sort-float

图 3.2-3

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