rust-algorithms:11-快速排序
0 / 0 / 创建于 2年前 /
godme 的个人博客
pub fn quick_sort<T: PartialOrd>(arr: &mut [T]) {
let len = arr.len();
if len > 1 {
quick_sort_range(arr, 0, len - 1);
}
}
fn quick_sort_range<T: PartialOrd>(arr: &mut[T], low: usize, high:usize) {
if low < high {
let partition = partition(arr, low, high);
if partition > 0 {
quick_sort_range(arr, low, partition);
}
quick_sort_range(arr, partition + 1, high)
}
}
fn partition<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) -> usize {
use rand::Rng;
// 随机数增加效率
let r = rand::thread_rng().gen_range(low..=high);
arr.swap(low, r);
let (
// 选取的值左边必定小于等于该值，可以放在最左端躲藏，避免重复移动
pivot,
mut left,
mut right
) = (
low,
low,
high
);
while left < right {
while left < right && arr[right] > arr[pivot] {
right -= 1;
}
while left < right && arr[left] <= arr[pivot] {
left += 1;
}
// 交换两端的差异值
if left != right {
arr.swap(left, right);
}
}
// 选取的值放在最中间，保证分割线
arr.swap(pivot, left);
left
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号