算法图解 - 快速排序

🏷️ 《算法图解》

分而治之

分而治之（divide and conqure，D&C） -- 一种著名的递归式问题解决方法
使用 D&C 解决问题的过程包含两个步骤
1. 找出基线条件，这种条件必须尽可能简单
2. 不断将问题分解（或者说缩小规模），直到符合基线条件

快速排序

工作原理
1. 从数组中选择一个元素，这个元素被称作基准值
2. 找出比基准值小的元素及比基准值大的元素，这被称为分区（partitioning）
3. 对 2 中找到的比基准值小的元素和比基准值大的元素分别重复执行 1，2 步骤，直到数组的长度小于 2
用 FlowChart 画了一个流程图，感觉不是很匹配，先凑活着看吧.
大 O 表示法
- 快速排序的最糟糕情况下，运行时间为 $O (n^{2})$
- 在平均情况下，运行时间为 $O (n l o g_{2} n)$
- 只要每次随机地选择一个数组元素作为基准值，快速排序的平均运行时间就将为 $O (n l o g_{2} n)$
快速排序是最快的排序算法之一，也是 D&C 的典范