快速排序算法中使用大小和索引的类型问题

Question

我正在尝试用 rust 实现快速排序算法，问题是，我有一个名为“ i ”的 var，它用作迭代器，但首先，它的值为“-1”，并且我无法将其设置为使用 isize 类型，因为它是负数，但我也无法将其设置为 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。实际上并不需要此更改，但它使代码更易于阅读。）