快速排序算法总结

文章目录

1. 1. 单向扫描
2. 2. 双向扫描
3. 3. 三中值扫描

本文首先分别详细阐述了单向扫描、双向扫描快速排序算法原理,并用golang分别设计实现了这两种经典的快速排序算法; 然后本文从性能的角度分不同场景进一步讨论了快速排序改进算法并在文中通过程序设计实现了相关算法，最后基于上述场景从上述算法总结了快速算法的特性及适用场景;

快速排序是对冒泡排序的一种改进, 采用分治策略, 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

下面首先来阐述快排的两种经典实现方式: 单向扫描及双向扫描,

单向扫描

算法原理: 主要由两部分组成, 一部分是递归部分QuickSort, 它将调用partition进行划分, 并取得划分元素P, 然后分别对P之前的部分和P 之后的部分递归调用QuickSort; 另一部分是partition, 选取划分元素P（随机选取数组中的一个元素, 交换到数组末尾位置）, 定义两个标记值left和right, 随着划分的进行, 这两个标记值将数组分成三部分, left之左的部分是小于划分元素P的值, left和right之间的部分是大 于等于划分元素P的值（等于p的值没有必要进行交换）, right之右的部分是未划分的部分。运行中right自左向右遍历, left指向最左的一个不小于P的值, 当right遇见小于P的元素就与left当前索引的值交换, right和left同时前进，否则right直接前进，直到数组末尾，最后将P与left当前指向的值交换, 并且返回i的值;

双向扫描

三中值扫描