rust - 快速排序算法中 Usize 和 Index 的类型问题

Question

我正在尝试用 Rust 实现快速排序算法，问题是，我有一个名为 'i' 的变量，用作迭代器，但起初，它的值为 '- 1'，我不能将它设置为 usize 类型，因为它是负数，但我也不能将它设置为 isize 类型，因为 isize 类型不能用作索引。

分区函数:

  fn partition(arr: &mut [isize], low: usize, high: usize) -> usize {
        let mut i: usize = low - 1; // when changed to isize, I do not encounter any errors but the algorithm itself doesnt work like it should.//
        let mut j: usize = low;
        let pivot: isize = arr[high];
        while j < high {
            if arr[j] <= pivot {
                i += 1;
                arr.swap(i, j);
            }
            j += 1;
        }
        arr.swap(i + 1, high);
        return i + 1;
    }

如果我尝试用另一个快速排序函数运行上面的代码，我得到的错误是:

thread 'main' panicked at 'attempt to subtract with overflow', src\functions.rs:2:24
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Answer 1

当然有很多方法可以解决这个问题。最简单的是让 i 从 low 而不是 low - 1 开始，并在交换后递增 i:

fn partition(arr: &mut [isize], low: usize, high: usize) -> usize {
    let mut i: usize = low;
    let pivot: isize = arr[high];
    for j in low..high {
        if arr[j] <= pivot {
            arr.swap(i, j);
            i += 1;
        }
    }
    arr.swap(i, high);
    return i;
}

这样，i 永远不会小于零，而代码仍然做同样的事情。

(请注意，我还使用了一个 for 循环来遍历 j 的值。这种更改并不是真正需要的，但它使代码更易于阅读.)