如何在Rust中按降序对向量进行排序？

Question

在Rust中，Vec的排序方法总是将元素从小到大排列。有没有一种通用的方式可以按从大到小的顺序排序呢？

如果您有一组数字的向量，您可以提供一个键提取函数来"反转"数字，就像这样:

let mut numbers: Vec<u32> = vec![100_000, 3, 6, 2];
numbers.sort_by_key(|n| std::u32::MAX - n);

但这并不十分清楚，而且将该方法扩展到其他类型（例如字符串）也不是很直观。

- nnnmmm

Answer 1

至少有三种方法可以实现。

翻转比较函数

vec.sort_by(|a, b| b.cmp(a))

这会改变元素比较的顺序，使得排序函数认为较小的元素更大，较大的元素更小。

使用反向Ord实例的包装器

use std::cmp::Reverse;
vec.sort_by_key(|w| Reverse(*w));

Reverse是一个通用的包装器，它具有与包装类型相反的排序顺序的Ord实例。

如果您尝试通过删除*来返回包含引用的Reverse，那么会出现生命周期问题，就像在sort_by_key中直接返回引用一样（也请参阅this question）。因此，此代码片段仅适用于键为Copy类型的向量。

先排序再翻转

vec.sort();
vec.reverse();

它最初按错误顺序排序，然后反转所有元素。

性能

我使用criterion对长度为100,000的Vec<u64>进行了三种方法的基准测试。计时结果按上述顺序列出。左右值分别显示置信区间的下限和上限，中间值是criterion的最佳估计。

性能相当，尽管翻转比较函数似乎稍微慢了一点：

Sorting/sort_1          time:   [6.2189 ms 6.2539 ms 6.2936 ms]
Sorting/sort_2          time:   [6.1828 ms 6.1848 ms 6.1870 ms]
Sorting/sort_3          time:   [6.2090 ms 6.2112 ms 6.2138 ms]

为了复现，将以下文件保存为benches/sort.rs和Cargo.toml，然后运行cargo bench。其中还有一个额外的基准测试，检查克隆向量的成本与排序相比是否无关紧要，它只需要几微秒。

fn generate_shuffled_data() -> Vec<u64> {
    use rand::Rng;
    let mut rng = rand::thread_rng();
    (0..100000).map(|_| rng.gen::<u64>()).collect()
}

pub fn no_sort<T: Ord>(vec: Vec<T>) -> Vec<T> {
    vec
}

pub fn sort_1<T: Ord>(mut vec: Vec<T>) -> Vec<T> {
    vec.sort_by(|a, b| b.cmp(a));
    vec
}

pub fn sort_2<T: Ord + Copy>(mut vec: Vec<T>) -> Vec<T> {
    vec.sort_by_key(|&w| std::cmp::Reverse(w));
    vec
}

pub fn sort_3<T: Ord>(mut vec: Vec<T>) -> Vec<T> {
    vec.sort();
    vec.reverse();
    vec
}

use criterion::{black_box, criterion_group, criterion_main, Criterion};

fn comparison_benchmark(c: &mut Criterion) {
    let mut group = c.benchmark_group("Sorting");
    let data = generate_shuffled_data();

    group.bench_function("no_sort", |b| {
        b.iter(|| black_box(no_sort(data.clone())))
    });

    group.bench_function("sort_1", |b| {
        b.iter(|| black_box(sort_1(data.clone())))
    });

    group.bench_function("sort_2", |b| {
        b.iter(|| black_box(sort_2(data.clone())))
    });

    group.bench_function("sort_3", |b| {
        b.iter(|| black_box(sort_3(data.clone())))
    });

    group.finish()
}

criterion_group!(benches, comparison_benchmark);
criterion_main!(benches);

[package]
name = "sorting_bench"
version = "0.1.0"
authors = ["nnnmmm"]
edition = "2018"

[[bench]]
name = "sort"
harness = false

[dev-dependencies]
criterion = "0.3"
rand = "0.7.3"

- nnnmmm

---

顺序排序后再进行反转通常不等同于按倒置比较器进行排序。相等的键的顺序可能会有所不同，在某些情况下可能很重要。 - algmyr

这三个中，看起来只有前两个是稳定的。 - BallpointBen

我认为std::cmp::Reverse是一个非常优雅的解决方案，用于反转排序。 - Ian Rehwinkel