rust的排序

Vec 中的 Methods from Deref

示例

fn main() {
    let mut strings = vec!["banana", "", "ban", "", "apple", "alpha", "cherry", "date"];

    strings.sort_by(|a, b| {
        if a.len() == 0 {
            return std::cmp::Ordering::Less;
        }
        if b.len() == 0 {
            return std::cmp::Ordering::Greater;
        }

        // pub fn chars(&self) -> Chars<'_> 返回一个基于字符数组之上的迭代器
        // fn next(&mut self) -> Option 通过迭代器遍字符
        let cmp = a.chars().next().unwrap().cmp(&b.chars().next().unwrap());
        if cmp == std::cmp::Ordering::Equal {
            a.len().cmp(&b.len())
        } else {
            cmp
        }
    });

    println!("{:?}", strings); // 输出：["alpha", "apple", "banana", "cherry", "date"]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

打印结果：[“”, “”, “apple”, “alpha”, “ban”, “banana”, “cherry”, “date”]

Slice

sort

pub fn sort(&mut self)
where
    T: Ord,
1
2
3

这种排序是稳定的（即，不会对相等的元素重新排序）并且最坏情况为 O(n * log(n))。
如果适用，首选不稳定排序（unstable sorting），因为它通常比稳定排序（stable sorting）更快，并且不分配辅助内存。

当前的算法是受 timsort 启发的自适应迭代合并排序。它被设计为在切片几乎是排好序或由两个或多个依次连接的排序序列组成的情况下非常快（ the slice is nearly sorted, or consists of two or more sorted sequences concatenated one after another.）。
此外，它分配的临时存储空间是 self 大小的一半，但对于短切片，则使用非分配插入排序（a non-allocating insertion sort）。

let mut v = [-5, 4, 1, -3, 2];

v.sort();
assert!(v == [-5, -3, 1, 2, 4]);
1
2
3
4

sort_by

pub fn sort_by<F>(&mut self, compare: F)
where
    F: FnMut(&T, &T) -> Ordering,
1
2
3

使用比较器函数（a comparator function）对切片进行排序。
这种排序是稳定的（即，不会对相等的元素重新排序）并且最坏情况为 O(n * log(n))。
比较器函数必须定义切片中元素的total ordering（define a total ordering for the elements in the slice）。如果排序不是全部，则元素的顺序未指定。total ordering的含义（对于所有 a、b 和 c）：

• 完全和反对称total and antisymmetric：a < b、a == b 或 a > b 中的一个为真，并且
• 传递transitive，a < b 和 b < c 意味着 a < c（同样适用于 == 和 >）

例如，虽然 f64 没有实现 Ord，因为 NaN != NaN，但当我们知道切片不包含 NaN 时，可以使用partial_cmp 作为排序函数。

let mut floats = [5f64, 4.0, 1.0, 3.0, 2.0];
floats.sort_by(|a, b| a.partial_cmp(b).unwrap());
assert_eq!(floats, [1.0, 2.0, 3.0, 4.0, 5.0]);
1
2
3

// Panic
let mut floats = [5f64, std::f64::NAN, 4.0, 1.0, 3.0, 2.0];
floats.sort_by(|a, b| a.partial_cmp(b).unwrap());
println!("floats is {:?}", floats);
1
2
3
4

说明同上

let mut v = [5, 4, 1, 3, 2];
v.sort_by(|a, b| a.cmp(b));
assert!(v == [1, 2, 3, 4, 5]);

// reverse sorting
v.sort_by(|a, b| b.cmp(a));
assert!(v == [5, 4, 3, 2, 1]);
1
2
3
4
5
6
7

sort_by_key

pub fn sort_by_key<K, F>(&mut self, f: F)
where
    F: FnMut(&T) -> K,
    K: Ord,
1
2
3
4

使用键提取函数对切片进行排序。
这种排序是稳定的（即，不会对相等的元素重新排序），最坏情况为 O(m * n * log(n))，其中关键函数为 O(m)。
对于昂贵的键函数（例如，不是简单属性访问或基本操作的函数），sort_by_cached_key 可能会快得多，因为它不会重新计算元素键。

let mut v = [-5i32, 4, 1, -3, 2];

v.sort_by_key(|k| k.abs());
assert!(v == [1, 2, -3, 4, -5]);
1
2
3
4

可以理解为排序不是按照v中的元素来排序，而是把元素处理后再排序，最后排序完后，按照key的结果有序

sort_by_cached_key

pub fn sort_by_cached_key<K, F>(&mut self, f: F)
where
    F: FnMut(&T) -> K,
    K: Ord,
1
2
3
4

使用键提取函数对切片进行排序。
在排序过程中，每个元素最多调用一次 key 函数，通过使用临时存储来记住 key 评估的结果。关键函数的调用顺序未指定，并且在标准库的未来版本中可能会发生变化。
这种排序是稳定的（即，不会对相等的元素重新排序），最坏情况为 O(m * n + n * log(n))，其中关键函数为 O(m)。
对于简单的键函数（例如，属性访问或基本操作的函数），sort_by_key 可能会更快。

当前的算法基于 Orson Peters 提出的模式击败快速排序（ pattern-defeating quicksort），它将随机快速排序的快速平均情况与堆排序的快速最坏情况相结合，同时在具有某些模式的切片上实现线性时间。它使用一些随机化来避免退化情况，但使用固定种子始终提供确定性行为。
在最坏的情况下，算法会在 Vec<(K, usize)> 切片长度中分配临时存储。

let mut v = [-5i32, 4, 32, -3, 2];

v.sort_by_cached_key(|k| k.to_string());
assert!(v == [-3, -5, 2, 32, 4]);
1
2
3
4

什么是Methods from Deref

Deref 是一个trait，在Rust中被用于智能指针或其他类型上，以提供对目标类型 [T] 中方法的调用。

根据 Deref trait 文档，Deref trait 定义了一个方法 deref，该方法用于将类型转换为其目标类型。对于 Deref，目标类型为 [T]，意味着它将实现 deref 方法，用于将类型转换为 [T]。

这允许在实现了 Deref 的类型上，通过 * 运算符或使用智能指针解引用操作符 &，来访问目标类型中的方法。

示例

use std::ops::Deref;

fn main() {
    let vec = vec![1, 2, 3];

    // 将 Vec 转换为 &[i32]
    let slice: &[i32] = vec.deref();

    // 通过解引用操作符调用 &[i32] 的方法
    // slice 方法：
    // pub fn iter(&self) -> Iter<'_, T>
    // 
    // Iter结构体如下所示：
    // pub struct Iter<'a, T>
	// where
    //     T: 'a,
	// { /* private fields */ }

    let sum: i32 = slice.iter().sum();

    println!("Sum: {}", sum); // 输出：Sum: 6
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

使用 deref 方法将其转换为 &[i32] 类型的切片。
接下来，使用解引用操作符 *（deref 方法已自动完成解引用）来调用切片的 iter 方法，然后通过 sum 方法计算切片中元素的总和。

这只是 Deref trait 的用法之一，它为具备目标类型为 &[T]（切片）的智能指针或类型提供了方便的调用方式。