quicksort

快速排序是一种分而治之的排序算法。递归地，我们逐个解析数字数组，将所选参考元素中的数字按照较小和较大的顺序放置，并将参考元素本身插入到它们之间的截止位置。经过几次递归迭代后，您将得到一个排序列表。时间复杂度 O(n²)。

方案：

我们首先从外部获取元素列表，即排序边界。第一步，排序边界将从头到尾。
检查起始边界和结束边界是否相交；如果发生这种情况，则该结束了
从列表中选择某个元素并将其命名为数据透视
将其向右移动到最后一个索引处的末尾，这样就不会妨碍
创建一个*较小数字*仍等于零的计数器
从左到右循环遍历列表，直到引用元素所在的最后一个索引（包括该索引）
我们将每个元素与参考元素进行比较
如果小于参考值，则根据较小数字的计数器的索引进行交换。增加较小数字的计数器。
当循环到达支持元素时，我们停止并根据较小数字的计数器将支持元素与元素交换。
我们分别针对列表左侧较小的部分和列表右侧较大的部分分别运行该算法。
因此，由于检查点 2，所有递归迭代都将开始停止
获取排序列表

快速排序是由莫斯科国立大学的科学家 Charles Anthony Richard Hoare 发明的，他在学习俄语后，在 Kolmogorov 学院学习了计算机翻译以及概率论。 1960年，因政治危机离开苏联。

Rust 中的示例实现：


use rand::Rng;

fn swap(numbers: &mut [i64], from: usize, to: usize) {
    let temp = numbers[from];
    numbers[from] = numbers[to];
    numbers[to] = temp;
}

fn quicksort(numbers: &mut [i64], left: usize, right: usize) {
    if left >= right {
        return
    }
    let length = right - left;
    if length <= 1 {
        return
    }
    let pivot_index = left + (length / 2);
    let pivot = numbers[pivot_index];

    let last_index = right - 1;
    swap(numbers, pivot_index, last_index);

    let mut less_insert_index = left;

    for i in left..last_index {
        if numbers[i] < pivot {
            swap(numbers, i, less_insert_index);
            less_insert_index += 1;
        }
    }
    swap(numbers, last_index, less_insert_index);
    quicksort(numbers, left, less_insert_index);
    quicksort(numbers, less_insert_index + 1, right);
}

fn main() {
    let mut numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    let mut reference_numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

    let mut rng = rand::thread_rng();
    for i in 0..numbers.len() {
        numbers[i] = rng.gen_range(-10..10);
        reference_numbers[i] = numbers[i];
    }

    reference_numbers.sort();

  println!("Numbers           {:?}", numbers);
  let length = numbers.len();
  quicksort(&mut numbers, 0, length);
  println!("Numbers           {:?}", numbers);
  println!("Reference numbers {:?}", reference_numbers);

  if numbers != reference_numbers {
    println!("Validation failed");
    std::process::exit(1);
  }
  else {
    println!("Validation success!");
    std::process::exit(0);
  }
}

如果不清楚，我建议观看圣地亚哥大学 Rob Edwards 的视频 https://www.youtube.com/watch?v=ZHVk2blR45Q 最简单、一步步展示了算法的本质和实现。

链接

https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/quickSort

来源