算法|快速排序

2021/7/6 20:41:10

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

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

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

1. 算法思想

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

图1:快速排序

图1:快速排序

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

图2:稳定排序

图3:不稳定排序

图3:不稳定排序

2. 实现步骤

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

图4:序列分区

图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,在此鸣谢。 ↩︎ ↩︎



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


扫一扫关注最新编程教程