如何检查切片是否已排序？

Question

如何检查切片是否已排序？

假设一个接受切片的函数i32,是否有一种惯用的Rust检查切片是否已排序的方法？

fn is_sorted(data: &[i32]) -> bool {
    // ...
}

是否有可能推广上述方法以便接受迭代器？

fn is_sorted<I>(iter: I)
where 
    I: Iterator, 
    I::Item: Ord,
{
    // ...
}

Answer 1

我会抓住成对的元素并断言它们都在升序(或降序,取决于你的"排序"的顺序)顺序:

fn is_sorted<T>(data: &[T]) -> bool
where
    T: Ord,
{
    data.windows(2).all(|w| w[0] <= w[1])
}

fn main() {
    assert!(is_sorted::<u8>(&[]));
    assert!(is_sorted(&[1]));
    assert!(is_sorted(&[1, 2, 3]));
    assert!(is_sorted(&[1, 1, 1]));
    assert!(!is_sorted(&[1, 3, 2]));
    assert!(!is_sorted(&[3, 2, 1]));
}

通用迭代器同上:

extern crate itertools; // 0.7.8

use itertools::Itertools;

fn is_sorted<I>(data: I) -> bool
where
    I: IntoIterator,
    I::Item: Ord + Clone,
{
    data.into_iter().tuple_windows().all(|(a, b)| a <= b)
}

fn main() {
    assert!(is_sorted(&[] as &[u8]));
    assert!(is_sorted(&[1]));
    assert!(is_sorted(&[1, 2, 3]));
    assert!(is_sorted(&[1, 1, 1]));
    assert!(!is_sorted(&[1, 3, 2]));
    assert!(!is_sorted(&[3, 2, 1]));
}

也可以看看:

• slice :: chunks/windows是否有等效的迭代器来循环对,三元组等？

Answer 2

不需要具有Clone迭代器is_sorted实现。这是不依赖Rust的实现is_sorted：

fn is_sorted<I>(data: I) -> bool
where
    I: IntoIterator,
    I::Item: Ord,
{
    let mut it = data.into_iter();
    match it.next() {
        None => true,
        Some(first) => it.scan(first, |state, next| {
            let cmp = *state <= next;
            *state = next;
            Some(cmp)
        }).all(|b| b),
    }
}