算法|快速排序

本文主要是介绍算法|快速排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

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

1. 算法思想

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

图1：快速排序

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

图2：稳定排序

图3：不稳定排序

2. 实现步骤

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

图4：序列分区

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

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

---

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

\[\begin{aligned} &PARTITION(A,l,r) \\ &~~~~~~ p \leftarrow l \\ &~~~~~~iter \leftarrow p \\ &~~~~~~while ~~~iter<r \\ &~~~~~~~~~~~~if~~~A[iter]<A[r] \\ &~~~~~~~~~~~~~~~~~~swap(A[iter],A[p]) \\ &~~~~~~~~~~~~~~~~~~p \leftarrow p+1 \\ &~~~~~~~~~~~~iter \leftarrow iter+1 \\ &~~~~~~swap(A[p],A[r]) \\ &~~~~~~return ~~~p \end{aligned} \]

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

\[\begin{aligned} &QUICKSORT(A,l,r) \\ &~~~~~~ if~~~l<r \\ &~~~~~~~~~~~~p \leftarrow PARTITION(A,l,r) \\ &~~~~~~~~~~~~QUICKSORT(A,l,p-1) \\ &~~~~~~~~~~~~QUICKSORT(A,p+1,r) \\ \end{aligned} \]

---

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

测试参考解答

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

---

1. C, A, R, et al. Quicksort[J]. The Computer Journal, 1962, 5(1):10-16. ↩︎

2. 图片引自Wikipedia，在此鸣谢。 ↩︎

3. 图片引自tutorialspoint，在此鸣谢。 ↩︎ ↩︎

这篇关于算法|快速排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！