前言
快速排序是一种很重要的排序算法，我花了不少时间去理解并总结它，希望可以通过图文的方式让你快速理解快速排序，并能手撸一个快排。
快速排序简介
快速排序是一种很不错的排序算法，算法复杂度为n*logn。快排使用了分而治之的思想，每次排序是都找到一个基准（我们学习时经常使用第一个作为基准）,然后把小于基准的元素放到基准元素的左边，大于基准的元素放到基准元素的右边，这样一次排序下来，基准元素左边都是小于（等于）基准的数，基准右边的元素都是大于（等于）基准的元素了。快速排序关键点就是找到这样一个基准并将其放到恰到的位置。
算法思路
定义一个快速排序函数，arr是要排序的数组，l指向要排序的数组最左边的元素，r指向要排序的数组最右边的元素。
那么现在关键就是这么实现这个partition2函数
假设现在有一个数组arr[]：
我们每次都取第一个元素为基准元素，定义i指向基准的下一个元素位置，j指向最后一个元素的位置：
i 从左向右扫描，如果arr[i] <= v , i++
j从右向左扫描，如果 arr[j] > v ，j–
直到i指向一个大于v的元素，j指向一个小于j的元素，且 这个过程中 i <= j
此时i左边（除基准元素）都是小于v的，j右边都是大于v的，现在只需要交换arr[i]与arr[j]的位置，就可以把小于v的放左边，大于v的放右边，然后i++,j–
继续比较，此时arr[i] = 4 < 5,i++ ,arr[j] > 5 j–
到这里 i > j 了，退出循环，最后把基准v与arr[j]交换位置，即把v放到了小于v的元素的最后一个，此时一次快速排序就完成了。
代码实现
快速排序的几个问题
1、对于几乎有序的数组，快速排序返回的基准的位置都在第一个或很靠前的位置，使得对数组的切分不够平均，可能使得快速排序的时间复杂度退到o(n^2) , 对于这种情况，可以在排序时选取数组中的一个随机位置的数作为基准数。
2、对于数组中的元素有很多相等元素时，也会导致快排对数组的切分不平衡，此时快排的时间复杂度也可能退到o(n^2) , 对于这种情况，可以使用三路快速排序，把小于基准v的放左边，等于v的放中间，大于v的放右边，就避免了左右不平衡的问题。
3、在进行快排时候，当数比较少的时候，使用插入排序代替快排可提高算法效率。
三路快速排序
三路快速排序针对数组中有很多相等元素时照样能有很不错的效率，其主要思想就是将数组中的数分成三个部分：小于基准v的放左边，等于v的放中间，大于v的放右边。
代码