如何用rust写一个快速排序算法
要用 Rust 写一个快速排序算法,首先需要了解快速排序的基本思想。
快速排序是一种分治算法,它的基本思路是:
- 从数列中选取一个元素(通常选择第一个元素)作为基准值。
- 将数列中小于基准值的元素放到基准值的左边,大于基准值的元素放到基准值的右边。
- 对基准值左右两侧的子数列分别递归执行步骤 1 和 2,直到所有的子数列都有序为止。
示例代码如下:
fn quick_sort(arr: &mut [i32]) {
if arr.len() <= 1 {
return;
}
let pivot = arr[0];
let mut left = 0;
let mut right = arr.len() - 1;
while left < right {
while left < right && arr[right] >= pivot {
right -= 1;
}
arr[left] = arr[right];
while left < right && arr[left] <= pivot {
left += 1;
}
arr[right] = arr[left];
}
arr[left] = pivot;
quick_sort(&mut arr[0..left]);
quick_sort(&mut arr[left+1..]);
}
在上面的代码中,arr
是要排序的数组,pivot
是基准值,left
和 right
分别表示基准值左右两侧的子数列。
执行过程中,会不断交换数组中小于基准值的元素和大于基准值的元素的位置,直到最后将基准值放到了它的正确位置。最后,递
还没有评论,来说两句吧...