数据结构_排序_快速排序
定义
- 将任务进行分割，然后各个击破
-
在某种特定的情况下，是最快的算法 - 基本原理：
- 设定一个基准值（也就是轴）
- 将比轴小的值，移到轴的左边，形成左子数列
- 将比轴大的值，移到轴的右边，形成右子数列
- 分别对左子数列和右子数列做上述
三个步骤(递归)，直到左子数列或右子数列只剩一个值或没有数值
- 快速排序的效率：选择的基准值越接近数列平均值越好
- 基准值（轴）的选择方式：
- 固定位置：第一位，或者最后一位
- 随机选择一位
- 随机取三个值，然后取中间值
- 不稳定算法
算法实现
<img src="https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/sort_fast_1.png" width="500" />
<img src="https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/sort_fast_2.png" width="500" />
代码中，Partition函数实现了排序和形成左右子数列，是快速排序的关键，下图展示了该函数第一次执行的过程，便于大家理解快速排序
<img src="https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/sort_fast.png" width="400" />
