目录
快速排序是什么？
快速排序的三种方法！
快速排序的优化
1.hore法（初代目）
hore法的源码
源码解析
2.挖坑法（常用）！！！！
挖坑法源码
3.前后指针法 （常用）
前后指针代码
4.非递归法
快速排序全过程图
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法
快速排序顾名思义，快速的排序，事实也如此，他的应用面广泛同时确实很快，因为他的时间复杂度是o（nlogn），相比前面的（插入冒泡选择）三小只来说，它的速度确实遥遥领先，但相对的思想也更复杂。
它的主要思想白话来说，就是
1.选择一个数据mid（中间人），以他为基准，
2.将剩下的数据比他小的放在左边，比他大的放在右边，
就像你开了一个宴会聘请四方，不止来了老一辈的投资人，还有新时代的年轻创业者们，因为有代沟自然分为了两边，而你就是中间那个负责笼络介绍的。但这个只是第一步（之后还要重复这一步）。下面的三种方法会详细解析全步骤。
快速排序的优化
因为我们要找到中间值所以可以采用三数取中的算法，就是从第一个 和 中间值 和 最后一个数据中选择三个数字的中间值。
解释：如果一个数组是有序的，1 2 3 4 5 6 7 8 9 10.这时候如果还是取1 为中间值，那就会导致最开始的分组就没有比1 小的数字，这样一组一组的往下走，时间一定特别久。所以如果用三数取中 取到 5那就不会出现这种情况了。
1.hore法（初代目）
第一层：原理
初代目的方法就是，以数组的第一个值作为中间人mid（key），通过和这个中间人比较大小，分出两边，就如上面说的投资派，和创业派。
但你发现这也没有序啊，之后分为两边后，然后在继续划分，取左边的第一个数字作为中间人，然后再分为两边，分到只剩下一个数据后，开始返回。最终返回一个有序的数组。右边也是同理，然后把左右和一开始的中间人组合起来就是一个有序的数组。
第二层：如何交换数据（关键）
查找过程先从后面开始遍历找到一个比key中间值小的数字，然后再从第二个数据开始遍历找到一个大于key的数字，然后交换数字，直到L和R相遇一趟排序结束。
第三层：为什么end（right）先走。
为什么要从right开始，因为你的key在数组的第一个位置，所以最后一次和key交换的数据一定要是比key小的。
如果left（begin）先走，如果只有最后一个数字比key大这时begin 和 end 相遇，反而把key换到了最后一个位置，而唯一比key大的数字反而去了第一个，那就不满足，左小右大的原则了
hore法的源码
源码解析
先用三数取中取到中间数。begin < end 即相遇停止，为什么第二个第三个while中也有begin < end 呢？是为了防止end 或者 begin 相遇后继续往前走。
第二个条件就是找大找小，然后再把找到的大小交换。直到begin 和 end 相遇。
最后交换第一个数字和二者（begin 和 end）相遇的位置。
同时记得交换其中的值。
如果只交换了值没有把位置交换，就会导致key还是在 下标为 0 的位置，接下来在递归时出错。
因为快排不是单趟而是要分大小组。所以这个递归很像二叉树的前序遍历，从左边小的开始（当然也可以从大的开始）先把一边排序好，再排另一边。
但对于hore初代目法来说，因为它里面的坑太多就导致一般不用它，而是后面的两种方法
2.挖坑法（常用）！！！！
挖坑法如名字一样：
第一步：挖坑，进墓
将第一个数字给挖出来用一个槽子装着（将其赋值给一个临时变量）这个值我们叫做key
以它作为探宝仪
第二步：寻宝，弃杂物。
这里我把大于key的值比作宝，把小于key的值比作杂物。
目前面前有10个物品，你站在右边从最后一个物品开始测试，前两个 8 10 大于key，那就摆着不动找到一个质量低于6，将它放在刚刚取走探宝仪的地方。现在高质量这边就少了一个了
可是我又是一个强迫症
于是我返回左边，又开始找质量大于6的。走了两步找到一个质量7的，我就把它摆在刚刚缺的位置。
就这样重复直到左右都找完了找到最后一个肯定是小于6的（上一个解法的最后有解释）。将他们进行交换。
这样第一趟就结束了，但我发现好像每个位置都是有个标号而且还是排序好的。强迫症的我，继续用这样的方式，将大小分边，直到两边都排好序。最后排好后，密室打开了。恭喜你解锁快排。
置于为什么这个是常用的呢？因为hore法的坑太多，所以常用的是这个。
挖坑法源码
1.取key值。
2.循环条件和之前一样；直到二者相遇，相遇后不改变。找大找小。
3.每次交换后更换坑（hole）的位置。
4.最后的坑位就是二者相遇的位置。这个坑的位置填上key即可。返回每次的坑位。
3.前后指针法 （常用）
1.前后指针法：
还是和挖坑法一样，前后指针还是盗慕，不过这次带了一个跟班。
这里prev 为跟班 而 cur 就是我。
宝藏开启的钥匙key现在等于6，现在要做的就是找到小于key和大于key的开门条件。
cur负责在前面走，找到大的话cur就继续走，这时prev不动。直到我找到一个小的，
我让prev向前走一步，如何我把小的开门条件扔给prev，让他装上，然后他把他脚下的大的开门条件扔给我，我在装上（这里相当于prev和cur上的值交换）。tips：因为cur之前走到大的时候没让prev动，所以prev的下一步只有两种情况（1.是大的开门条件2.cur的上一步）
如何我继续往前找小，每次找到小就让prev往前走，让其把小的开门条件装上去。我再把大的开门条件装上去，这样直到我走完，这时prev还是在最后一个小的开门条件上。这时把key和prev交换（因为第一个位置的小开门条件还没装上），就可以把大于key和小于key的值分开了。最后将prev位置上的拿回去装上，再把key拿过来开门，就解决了。
2.快速排序：
我们现在把门打开了，发现还是不行，现在不再是一排，而是分成了两排。
其中每一排的数量刚好等于刚刚大于key的开门条件和小于key的开门条件的数量。
我也反应过来这是要再按刚刚的方法在进行一次。就这样无限套娃。
直到全部有序。才拿到宝物。
前后指针代码
4.非递归法
非递归法需要用到栈来实现。
非递归：
就是用栈模拟递归的过程，每次压进去的都是区间的范围，通过区间范围，对这个区间再次进行partsort。