如何比较 i32 和 usize

Question

我正在编写一个简单的插入排序。下面是相关代码。

fn main() {
    let mut sort_vec = vec![5,2,4,6,1,3];

    for j in 1..sort_vec.len() {
        let key = sort_vec[j];
        
        let mut i = j - 1;
        
        while i > 0 && sort_vec[i] > key {
            sort_vec[i+1] = sort_vec[i];
            i = i - 1;
        }
        sort_vec[i+1] = key;
    }
    println!("{:?}",sort_vec);
}

它的输入是[5, 1, 2, 3, 4, 6].

问题是当 while i > 0 变为 while i >= 0 或 while i > -1 ，不行。

那么i32和usize比较有问题吗？我尝试了一些方法，但无法成功。那我应该怎么处理呢？不胜感激！

Answer 1

Here 有一个很好的技巧（请注意，在 Rust 中，包装算法必须是显式的，否则它会在调试模式下崩溃）：

while i < j && sort_vec[i] > key {
    sort_vec[i + 1] = sort_vec[i];
    i = i.wrapping_sub(1);
}
sort_vec[i.wrapping_add(1)] = key;

Playground.

我们的想法是让 i 下溢然后溢出回来 - 但当它下溢时它将不再小于 j，因此循环将停止。

Answer 2

如果您将 while i > 0 更改为 while i >= 0，编译器会给您一个警告：

warning: comparison is useless due to type limits
--> src\main.rs:9:15
  |
9 |         while i >= 0 && sort_vec[i] > key {
  |               ^^^^^^
  |
  = note: `#[warn(unused_comparisons)]` on by default

并且代码在运行时崩溃： thread 'main' panicked at 'attempt to subtract with overflow', src\main.rs:11:17

问题是如果 i 下降到 0 而你试图减去 1，整数 i 会溢出，因为它的类型是 usize，必须是非负数。因为 usize 不能为负，所以您的比较 i >= 0 始终为真（这是编译器警告）。

我建议稍微改变一下逻辑：不要将倒数第二个元素与下一个元素进行比较，而是将最后一个元素与前一个元素进行比较。因此，您必须不是从 j - 1 开始，而是从 j 开始，并因此在每个索引中的以下行 i 中替换为 i - 1:

sort_vec[i] -> sort_vec[i - 1]
sort_vec[i + 1] -> sort_vec[i]

工作代码：

fn main() {
    let mut sort_vec = vec![5, 2, 4, 6, 1, 3];

    for j in 1..sort_vec.len() {
        let key = sort_vec[j];

        let mut i = j;

        while i > 0 && sort_vec[i - 1] > key {
            sort_vec[i] = sort_vec[i - 1];
            i = i - 1;
        }
        sort_vec[i] = key;
    }
    println!("{:?}", sort_vec);
}

现在您可以看到不必要的赋值 let mut i = j。您可以将 for 循环的头部更改为 for mut j in ... 以删除它并将所有 i 替换为 j.

fn main() {
    let mut sort_vec = vec![5, 2, 4, 6, 1, 3];

    for mut j in 1..sort_vec.len() {
        let key = sort_vec[j];

        while j > 0 && sort_vec[j - 1] > key {
            sort_vec[j] = sort_vec[j - 1];
            j = j - 1;
        }
        sort_vec[j] = key;
    }
    println!("{:?}", sort_vec);
}

Answer 3

i 的类型为 usize，因此 永远不会 小于 0。因此 i >= 0 或 i >= -1 是总是正确的。解决问题的一种方法是使用具有反向范围的 for 循环：

fn main() {
    let mut sort_vec = vec![5, 2, 4, 6, 1, 3];

    for j in 1..sort_vec.len() {
        for i in (0..j).rev() {
            if sort_vec[i+1] < sort_vec[i] {
                sort_vec.swap (i, i+1);
            } else {
                break;
            }
        }
    }
    println!("{:?}", sort_vec);
}

Playground

如何比较 i32 和 usize

How to compare i32 with usize

compare

insertion-sort

rust