算法图解 - 快速排序

🏷️ 《算法图解》

分而治之

• 分而治之（divide and conqure，D&C） -- 一种著名的递归式问题解决方法

• 使用 D&C 解决问题的过程包含两个步骤

  1. 找出基线条件，这种条件必须尽可能简单

  2. 不断将问题分解（或者说缩小规模），直到符合基线条件

快速排序

• 工作原理

  1. 从数组中选择一个元素，这个元素被称作基准值

  2. 找出比基准值小的元素及比基准值大的元素，这被称为分区（partitioning）

  3. 对 2 中找到的比基准值小的元素和比基准值大的元素分别重复执行 1，2 步骤，直到数组的长度小于 2

  用 FlowChart 画了一个流程图，感觉不是很匹配，先凑活着看吧.

  

• 大 O 表示法

  • 快速排序的最糟糕情况下，运行时间为 $O(n^2)$

  • 在平均情况下，运行时间为 $O(nlo{g}_{2}n)$

  • 只要每次随机地选择一个数组元素作为基准值，快速排序的平均运行时间就将为 $O(nlo{g}_{2}n)$

• 快速排序是最快的排序算法之一，也是 D&C 的典范