sorting - Rust 排序使用的比较少得惊人

Question

我目前正在学习 Rust(使用 Rust 书)和 one page提到计算排序数组时使用排序键的次​​数。我修改了代码以便计算任意大小的代码，这里是代码:

fn main() {
    const MAX: i32 = 10000;
    for n in 1..MAX {
        let mut v: Vec<i32> = (1..n).collect();
        let mut ops = 0;
        
        v.sort_by(|x, y| {
            ops += 1;
            x.cmp(y)
        });
        
        if n-2 >= 0 {
            assert_eq!(n-2, ops);
        }
        // println!("A list of {n} elements is sorted in {ops} operations");

    }
}

然而，为了对 n 个元素的向量进行排序，Rust 似乎只需要 n-2 次比较(上面的代码运行时没有出现 panic )。这怎么可能 ？排序不应该在 O(n*log(n)) 中吗？是因为 Rust 以某种方式“注意到”我的输入向量已经排序了吗？

即使在那种情况下，如何在没有任何比较的情况下对长度为 2 的向量进行排序？至少不应该是 n-1 吗？

Answer 1

我认为你最大的误解是:

fn main() {
    const SIZE: i32 = 5;
    let v: Vec<i32> = (1..SIZE).collect();
    println!("{}", v.len());
}

4

范围 1..SIZE 不包括 SIZE 并且包含 SIZE-1 元素。此外，它已经被排序，所以它就像迭代一次一样简单。

看这里:

fn main() {
    const SIZE: i32 = 5;

    let mut v: Vec<i32> = (1..SIZE).collect();
    let mut ops = 0;

    v.sort_by(|x, y| {
        ops += 1;
        let result = x.cmp(y);
        println!(" - cmp {} vs {} => {:?}", x, y, result);
        result
    });

    println!("Total comparisons: {}", ops);
}

 - cmp 4 vs 3 => Greater
 - cmp 3 vs 2 => Greater
 - cmp 2 vs 1 => Greater
Total comparisons: 3

---

it seems that in order to sort a vector of n elements, Rust only needs n-2 comparaisons

这是不正确的。为了对一个已经排序的向量(你的)进行排序，Rust 需要n-1 比较。它不会检测到，这只是 Rust 使用的合并排序实现的固有属性。

如果还没有排好序，那就多了:

fn main() {
    let mut v: Vec<i32> = vec![2, 4, 1, 3];

    let mut ops = 0;

    v.sort_by(|x, y| {
        ops += 1;
        let result = x.cmp(y);
        println!(" - cmp {} vs {} => {:?}", x, y, result);
        result
    });

    println!("Total comparisons: {}", ops);
}

 - cmp 3 vs 1 => Greater
 - cmp 1 vs 4 => Less
 - cmp 3 vs 4 => Less
 - cmp 1 vs 2 => Less
 - cmp 3 vs 2 => Greater
Total comparisons: 5