概念
- 通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的;
- 是冒泡排序的一种升级;
- 将任务进行分割，然后各个击破
-
在某种特定的情况下，是最快的算法 - 基本原理：
- 设定一个基准值（也就是轴）
- 将比轴小的值，移到轴的左边，形成左子数列
- 将比轴大的值，移到轴的右边，形成右子数列
- 分别对左子数列和右子数列做上述
三个步骤(递归)，直到左子数列或右子数列只剩一个值或没有数值
- 快速排序的效率：选择的基准值越接近数列平均值越好
- 基准值（轴）的选择方式：
- 固定位置：第一位，或者最后一位
- 随机选择一位
- 随机取三个值，然后取中间值
- 不稳定算法;
- 时间复杂度：O(nlogn);
算法实现
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-quick-1.png" width="500" />
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-quick-2.png" width="500" />
代码中，Partition函数实现了排序和形成左右子数列，是快速排序的关键，下图展示了该函数第一次执行的过程，便于大家理解快速排序
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-quick-3.png" width="500" />
