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

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

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容