数据结构_排序_快速排序

github地址：
https://github.com/arkulo56/thought/blob/master/software/dataStruct/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E6%8E%92%E5%BA%8F_%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F.md

数据结构_排序_快速排序

定义

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

算法实现

<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" />