插入排序算法会产生溢出错误

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 
}