快速排序

桶排序占用空间太大？快速排序太慢？有没有更好的排序算法呢？答案肯定是有的。

它就是快速排序。

---

---

快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。

快速排序典型的用到了分治算法，至于分治算法是什么以后再为大家来介绍。

学懂快速排序只需要三步：

1. 先从数列中取出一个数作为基准数；

2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边；

3. 再对左右区间重复第二步，直到各区间只有一个数；

我们来规定一下基准数，在这里我们把待排序数列的第一个数字当做基准数。

选好了基准数如何分区呢？

我们可以写一个双指针扫描。左指针找大于基准数的数字，右指针找小于基准数的数字，如果右指针指向元素的下标大于左指针指向元素的小标，那么就交换元素。再把基准数交换到分界处，然后把这段数分成两段，一段是[头，基准数]，另一段是[基准数+1，尾]。

可以上代码了