快速排序又叫quick sort，是一种比较高效的排序算法，其核心思想可以理解为是结合了分治法的排序

其基本的算法思路为：

①、先选择一个基数，这个基数可以是数组任意一个元素。 ②、设定两个指针，一个指针指向数组的头部，一个指针指向数组的尾部 ③、首先让尾指针向左移动，移动的条件是：如果左边的元素大于或等于基数，继续移动，否则，停止移动 ④、当第三步的尾指针停止移动时，头指针才开始向右移动，如果右边的元素小于或等于基数，继续移动，否则，停止移动 ⑤、如果头指针与尾指针都停止移动，而且两个指针没有相遇，则交换两个指针所指向数组的值，然后在现在的位置上继续重复第③、④、⑤步 ⑥、最终，当两个指针发生相遇的时候，交换相遇处的值与基数的值，此时一轮排序结束 ⑦、一轮排序结束后，此时基数被替换到了某个位置，假设为 i 位置，此时可以发现 i 左边的所有数都小于i所指向的数组值，同理 i 右边的都大于 ⑧、此时将i左边和i右边的区域划分为两个子数组，继续重复上面的步骤，直到所有子序列都经过排序。 ⑨、最终完成所有，数组排序成功。 值得一提的是，如果是数组从小到大排序，则比基数小的数放左边，比基数大的数放右边，如果是从大到小排序，则相反即可。

看上去有点复杂，没事，下面直接开始最通俗易懂的图解方法： 排序数组 [0,0,2,3,2,1,2,4]，排序方式：递增排序

第一步，先让尾指针向前移动，直到找到第一个小于基数的数或者与i重合的时候才停止 很明显结果如下，停止的条件是i 和 j 重合了

由于两个指针发生了相遇，所以此时应该交换相遇处的值与基数的值，发现基数值与 相遇的值是同一个位置的值，则忽略交换（因为此时交换没有任何意义） 接下来，划分子数组区域继续排列 此时 i = 0，j = 0 ，而划分区域的公式为: (len是原数组长度，而且此时 i 必然等于 j) 左边子区域 [ 0 , i − 1 ] ，右边的子区域 [ i + 1 , l e n − 1 ] 左边子区域 [0, i-1]，右边的子区域 [i + 1, len - 1] 左边子区域[0,i−1]，右边的子区域[i+1,len−1] 划分的结果 左边子区域 : [ ] ，右边的子区域 : [ 0 , 2 , 3 , 2 , 1 , 2 , 4 ] 左边子区域 :[]，右边的子区域 :[0,2,3,2,1,2,4] 左边子区域:[]，右边的子区域:[0,2,3,2,1,2,4]

按照上面的方法，不难看出此时的排序结果为如下

此时的排序结果我们就需要注意一下了，跟上面两种方法的排序结果不一样 首先尾指针左移，第一个小于基数的元素是1，此时 j 停下来不动 然后头指针右移，第一个大于基数的元素是3，此时 i 停下来不动 如下结果 可以看到，此时的 i 与 j 并没有发生碰撞，怎么办呢，交换i和j的元素即可，交换后如下 继续让重复下面操作 首先尾指针左移，第一个小于基数的元素是1，此时 j 停下来不动 i 与 j 已经发生了碰撞，此时 i 不需要移动 交换 i上的数与基数 到这里，这一轮就交换完成了，下面我们继续在这个子数组的基础上再划分左右子数组

到这里相信大家差不多都了解了，有限划分左右子区，一直迭代下去，是一个递归的过去 接下来的步骤大家可以手动自己试试！ O(∩_∩)O哈哈~

到处，快速排序的演示就结束了 😄

c++代码如下