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

╰半夏微凉° 2024-03-27 12:38 131阅读 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 是基准值，left 和 right 分别表示基准值左右两侧的子数列。

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

发表评论

表情：
评论列表 （有 0 条评论，131人围观）

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

相关阅读