快速排序 详解（快速排序 双路快排 三路快排）

注：内容，图片来自于慕课网liuyubobobo老师的课程。

 官方代码链接：https://github.com/liuyubobobo/Play-with-Algorithms

快速排序

快速排序可以说是20世纪最伟大的算法之一了。相信都有所耳闻，它的速度也正如它的名字那样，是一个非常快的算法了。当然它也后期经过了不断的改进和优化，才被公认为是一个值得信任的非常优秀的算法。

c++中algorithm中的sort一般都是用的快排（在快排恶化的情况下才会转换成其它的排序）。

核心思想：分治

下面我们来讲解一下快排的子过程的思路：

快速排序是把数组中的一个元素挪到它排好序时应该所处的位置，如图：

首先选择数组中的一个元素，比如用l索引指向最左边的元素v，逐渐遍历数组所有位于l左边的元素，在遍历的过程中，我们将逐渐整理出小于v的元素和大于v的元素，当然我们继续用一个索引j来记录小于v和大于v的分界点，然后我们当前访问的元素索引为i。

那么i怎么处理呢？很简单当i指向的元素e大于v的时候，直接包含进大于v的部分中，像这样：

然后我们继续讨论下一个元素，此时i++，如图：

如果元素e小于v的时候怎么做呢&