排序-快速排序

概念

• 通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的;
• 是冒泡排序的一种升级;

• 将任务进行分割，然后各个击破
• 在某种特定的情况下，是最快的算法
• 基本原理：
  • 设定一个基准值（也就是轴）
  • 将比轴小的值，移到轴的左边，形成左子数列
  • 将比轴大的值，移到轴的右边，形成右子数列
  • 分别对左子数列和右子数列做上述三个步骤(递归)，直到左子数列或右子数列只剩一个值或没有数值
• 快速排序的效率：选择的基准值越接近数列平均值越好
• 基准值（轴）的选择方式：
  • 固定位置：第一位，或者最后一位
  • 随机选择一位
  • 随机取三个值，然后取中间值
• 不稳定算法;
• 时间复杂度：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" />

完整代码实现