插入排序算法會產生溢出錯誤

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 
}