为什么插入排序算法会出现溢出错误？

Question

当尝试运行插入排序算法时，如 Rust 1.15 所示。

fn main() {
    println!("The sorted set is now: {:?}", insertion_sort(vec![5,2,4,6,1,3]));
}

fn insertion_sort(set: Vec<i32>) -> Vec<i32> {
    let mut A = set.to_vec();
    for j in 1..set.len() {
        let key = A[j];
        let mut i = j - 1;
        while (i >= 0) && (A[i] > key) {
            A[i + 1] = A[i];
            i = i - 1;
        }
        A[i + 1] = key;
    }
    A
}

我收到错误：

thread 'main' panicked at 'attempt to subtract with overflow', insertion_sort.rs:12
note: Run with `RUST_BACKTRACE=1` for a backtrace

为什么这里会发生溢出以及如何修复它？

Answer 1

原因是您尝试以

0 - 1

类型计算

usize

，该类型是无符号（非负）的。这可能会导致 Rust 出现错误。

为什么

usize

？因为 Rust 期望长度和索引为

usize

。您可以显式地将它们转换为签名的签名或从签名的签名转换为签名的签名。

isize

。

fn main() {
    println!("The sorted set is now: {:?}", insertion_sort(vec![5,2,4,6,1,3]));
}

fn insertion_sort(set: Vec<i32>) -> Vec<i32> {
    let mut A = set.to_vec();
    for j in 1..set.len() as isize {
        let key = A[j as usize];
        let mut i = j - 1;
        while (i >= 0) && (A[i as usize] > key) {
            A[(i + 1) as usize] = A[i as usize];
            i = i - 1;
        }
        A[(i + 1) as usize] = key;
    }
    A
}

我推荐的另一个解决方案是完全避免负指数。在这种情况下，您可以使用

i + 1

代替

i

，如下所示：

fn main() {
    println!("The sorted set is now: {:?}", insertion_sort(vec![5,2,4,6,1,3]));
}

fn insertion_sort(set: Vec<i32>) -> Vec<i32> {
    let mut A = set.to_vec();
    for j in 1..set.len() {
        let key = A[j];
        let mut i = j;
        while (i > 0) && (A[i - 1] > key) {
            A[i] = A[i - 1];
            i = i - 1;
        }
        A[i] = key;
    }
    A
}