5.2.1. 整数 Vector 排序

std-badge cat-science-badge

问题:

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

解决方案:

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

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

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 进行排序。

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

  排序前: [1, 5, 10, 2, 15]
  排序后: [1, 2, 5, 10, 15]

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

讨论:

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

使用 vec::sort_unstable 对切片进行排序,但可能不会保留相等元素的顺序。这种排序类型不甚稳定(即,可能重新排序相等的元素)。