写一个三路快速排序的rust实现

以下是一个三路快速排序的Rust实现：

fn quicksort(arr: &mut [i32], left: usize, right: usize) {
    if left >= right {
        return;
    }

    let mut lt = left;
    let mut gt = right;
    let mut i = left + 1;
    let pivot = arr[left];

    while i <= gt {
        if arr[i] < pivot {
            arr.swap(lt, i);
            lt += 1;
            i += 1;
        } else if arr[i] > pivot {
            arr.swap(i, gt);
            gt -= 1;
        } else {
            i += 1;
        }
    }

    quicksort(arr, left, lt - 1);
    quicksort(arr, gt + 1, right);
}

fn main() {
    let mut arr = [5, 3, 8, 4, 2];
    quicksort(&mut arr, 0, arr.len() - 1);
    println!("{:?}", arr);
}

这个实现中，我们使用 `lt` 和 `gt` 指针来跟踪小于和大于枢轴元素的区间。我们遍历整个数组，如果当前元素小于枢轴元素，则将其与 `lt` 指针指向的元素交换，并将 `lt` 指针向右移动。如果当前元素大于枢轴元素，则将其与 `gt` 指针指向的元素交换，并将 `gt` 指针向左移动。如果当前元素等于枢轴元素，则继续向右遍历。

一旦我们完成了一次遍历，我们就可以将数组分成三部分：小于枢轴元素的区间、等于枢轴元素的区间和大于枢轴元素的区间。我们可以递归地对小于和大于枢轴元素的区间进行排序。

这种算法的时间复杂度为 $O(n \log n)$，空间复杂度为 $O(1)$。