算法|快速排序

大佬教程收集整理的这篇文章主要介绍了算法|快速排序，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

完成阅读您将会了解快速排序的：

1. 算法思想
2. 实现步骤
3. 实践范例（C++/Rust）

1. 算法思想

快速排序（Quick Sort），简称快排，最早由 C.A.R.Hoare 在1962年于快速排序^[1]一文提出。快速排序实质上运用分治（Divide & Conquer）思想，每次选取基准元素（Pivot Element），并将剩余元素在其左右分为小于与不小于基准元素的两个子序列（Sub-sequence），然后针对子序列递归地进行快速排序，如图1^[2]。

快速排序为不稳定排序（Unstable Sort），即同值元素排序后未必保持原有相对位置，如图2-3^[3]。快速排序时间复杂度为(O(n^2))，但实际运用中，摊销（Amortized）时间复杂度为(O(nlg n))。快速排序是一种原址排序（In-place Sort）算法，额外的空间复杂度为(Theta (1))。快速排序算法适合硬件高速缓存（Cache）优化，拥有很好的实际运行效率，并被广泛使用。

2. 实现步骤

1. 选择基准元素；（序列尾，本文程序范例中随机选取基准）
2. 将不小于和不大于基准元素的元素分区为左右两个子序列，与此同时基准元素本身已完成排序，如图4^[3:1]；
3. 递归排序子序列。

3. 实践范例（C++/Rust）

问题描述： 为无序数组A做单调不减排序。 输入：无序数组A 输出：有序数组A 解答思路： 运用快速排序算法对A进行原址排序。

伪代码1：分区 变量说明：A(rightarrow)待排序数组；l(rightarrow)子序列左闭边界；r(rightarrow)子序列右闭边界；p(rightarrow)分区点；iter(rightarrow)迭代替量

伪代码2：快速排序A 变量说明：A(rightarrow)待排序数组；l(rightarrow)子序列左闭边界；r(rightarrow)子序列右闭边界；p(rightarrow)分区点

C++解答：传指针入参

constexpr auto _partition(auto l, auto r) noexcept {
  auto p = l, iter = p - 1;
  auto pivot = *r;
  while (++iter < r)
    if (*iter < pivot)
      std::swap(*iter, *p++);
  std::swap(*p, *r);
  return p;
}

void quick_sort(auto l, auto r) noexcept {
  srand(time(nullptr));
  if (l < r) {
    std::swap(*(l + rand() % (r - l + 1)), *r);
    auto p = _partition(l, r);
    quick_sort(l, p - 1);
    quick_sort(p + 1, r);
  }
}

Rust解答：

fn _partition<T: Clone + std::cmp::PartialOrd>(A: &mut Vec<T>, l: usize, r: usizE) -> usize {
    let (mut p, pivot) = (l, A[r].clone());
    for i in l..r {
        if A[i] < pivot {
            A.swap(i, p);
            p += 1;
        }
    }
    A.swap(p, r);
    p
}

pub fn quick_sort<T: Clone + std::cmp::PartialOrd>(A: &mut Vec<T>, l: usize, r: usizE) {
    if l < r {
        A.swap(thread_rng().gen_range(l..=r), r);
        let mut p = _partition(A, l, r);
        quick_sort(A, l, p - 1);
        quick_sort(A, p + 1, r);
    }
}

4. 自我测试

伪代码实践： 快排递归版受栈内存限制，无法直接应用在大规模数据上，请将快排改写成迭代版。

LeetCode选荐：

1. Sort an Array

测试参考解答

让每一天足够精致，期待与您的再次相遇! ^_^

大佬总结

以上是大佬教程为你收集整理的算法|快速排序全部内容，希望文章能够帮你解决算法|快速排序所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。