如何用rust写一个快速排序算法

╰半夏微凉° 2024-03-27 12:38 132阅读 0赞

要用 Rust 写一个快速排序算法,首先需要了解快速排序的基本思想。

快速排序是一种分治算法,它的基本思路是:

  1. 从数列中选取一个元素(通常选择第一个元素)作为基准值。
  2. 将数列中小于基准值的元素放到基准值的左边,大于基准值的元素放到基准值的右边。
  3. 对基准值左右两侧的子数列分别递归执行步骤 1 和 2,直到所有的子数列都有序为止。

示例代码如下:

  1. fn quick_sort(arr: &mut [i32]) {
  2. if arr.len() <= 1 {
  3. return;
  4. }
  5. let pivot = arr[0];
  6. let mut left = 0;
  7. let mut right = arr.len() - 1;
  8. while left < right {
  9. while left < right && arr[right] >= pivot {
  10. right -= 1;
  11. }
  12. arr[left] = arr[right];
  13. while left < right && arr[left] <= pivot {
  14. left += 1;
  15. }
  16. arr[right] = arr[left];
  17. }
  18. arr[left] = pivot;
  19. quick_sort(&mut arr[0..left]);
  20. quick_sort(&mut arr[left+1..]);
  21. }

在上面的代码中,arr 是要排序的数组,pivot 是基准值,leftright 分别表示基准值左右两侧的子数列。

执行过程中,会不断交换数组中小于基准值的元素和大于基准值的元素的位置,直到最后将基准值放到了它的正确位置。最后,递

发表评论

表情:
评论列表 (有 0 条评论,132人围观)

还没有评论,来说两句吧...

相关阅读