请给我写一个rust 快速排序代码
时间: 2024-09-24 08:22:41 浏览: 44
当然可以,这里是一个简单的快速排序算法实现示例,使用 Rust 语言:
```rust
fn quick_sort<T: Ord>(arr: &mut [T]) {
if arr.len() <= 1 {
return;
}
let pivot = arr[arr.len() / 2];
let mut left = arr.split_off(0..arr.len() / 2);
let mut right = arr.split_off(arr.len() / 2 + 1..);
// 分区并递归排序左右两个部分
let (sorted_left, _) = quick_sort_partition(left, pivot);
let (_, sorted_right) = quick_sort_partition(right, pivot);
*arr = sorted_left.extend(sorted_right).collect();
}
fn quick_sort_partition<T: Ord>(slice: &mut [T], pivot: T) -> (&mut [T], &mut [T]) {
let len = slice.len();
let mut i = 0;
let mut j = len - 1;
while i < j {
while i < j && slice[i] <= pivot {
i += 1;
}
while i < j && slice[j] > pivot {
j -= 1;
}
if i != j {
swap!(slice, i, j);
}
}
(slice.split_at_mut(i), slice.split_at_mut(j + 1))
}
fn swap<T>(mut a: &mut T, b: usize) {
let temp = a.swap(b);
}
fn main() {
let mut array = vec![9, 7, 5, 11, 12, 2, 14, 3, 10];
println!("Before sorting: {:?}", array);
quick_sort(&mut array);
println!("After sorting: {:?}", array);
}
```
这个代码首先检查数组长度是否小于等于1,然后选择一个基准值(pivot),分割数组,并对左右两部分递归应用快速排序。`quick_sort_partition`函数用于分区操作。`main`函数展示了一个例子。
阅读全文