快速排序

D&C（分而治之）

工作原理：

1. 找出简单的基线条件；
2. 确定如何缩小问题的规模，使其符合基线条件

案例

对一块400m * 640m的土地进行划分

对于640 m × 400 m的土地，可从中划出的最 大方块为400 m × 400 m。 这将余下一块更小的土地，其尺寸为400 m × 240 m

重点：适用于这小块地的最大方块（正方形），也是适用于整块地的最大方块

这是关于“欧几里得算法”的知识

快速排序

简介：

采用分而治之的思想进行排序，是对冒泡排序算法的一种改进

步骤:

1) 选择基准值。

2) 将数组分成两个子数组：小于基准值的元素和大于基准值的元素。

3) 对这两个子数组进行快速排序。

代码实例

使用快速排序进行排序

1. 定义左数组存储比当前值小的值，右数组存储比当前数值大的值，以及当前比较目标值
2. 定义基线条件：当当前传参数组索引小于等于1时，停止执行下面代码并返回当前数组
3. 定义递归条件
   1. 截取当前数组内要进行比较的目标值，避免参与遍历导致无限循环
   2. 进行遍历：大于当前值放至右数组，小于当前值放至左数组
4. 返回左数组＋当前值+右数组

.png)

总结

1. D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组。
2. 实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)。
3. 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。
4. 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O(log n)的速度比O(n) 快得多。