快速排序的基本思想：通过一趟排序将待排序数据分隔为独立的两部分，其中的一部分数据均比另一部分小，则可分别对这两部分数据进行排序，以达到整个序列有序。
快速排序使用分治法把一个串分为两个子串。具体算法描述如下：
1、从数列中挑出一个元素，称为“基准”(pivot)
2、重新排序数列，所有元素比基准值小的摆放在基准的前面，所有元素比基准大的摆放在基准的后面(相同的数可以到任一边)。在这个分区退出之后，该基准就处于数列的中间位置。这个成为分区(partiton)操作
3、递归的把小于基准值元素的子数列和大于基准值元素的子数列排序。
//快速排序
func QuickSort(in []int, l, rint) {
if l < r {
var i,j,xint
i = l
j = r
x = in[i]
for i < j {
for i < j && in[j] > x {
j--
}
if i < j {
in[i]=in[j]
i++
}
for i < j && in[i] < x {
i++
}
if i < j {
in[j] = in[i]
j--
}
}
in[i] = x
QuickSort(in,l, i-1)
QuickSort(in, i+1,r)
}
}
下面以数列a={30,40,60,10,20,50}为例，演示它的快速排序过程(如下图)
上图只是给出了第一趟快速排序的流程。在第一趟中，设置x=a[i],即x=30.
1、从“右-->左”查找小于x的数；找到满足条件的数a[j]=20,此时j=4；然后将a[j]赋值给a[i]，此时i=0；接着从左往右遍历。
2、从“左-->右”查找大于x的数；找到满足条件的数a[i]=40,此时i=2；然后将a[i]赋值给a[j]，此时j=4；接着从右往左遍历。
3、“右-->左”查找小于x的数；找到满足条件的数a[j]=10，此时j =3；然后将a[j]赋值给a[i],此时i=1；接着从左往右遍历
4、从“左-->右”查找大于x的数；找到满足条件的数a[i]=60，此时i=2；然后将a[i]赋值给a[j],此时j=3；接着从右往左遍历
5、从“右-->左”查找小于x的数；没有找到满足条件的数。当i>=j时，停止查找；然后将x赋值给a[i]。此趟遍历结束！
按照同样的方法，对子数列进行递归遍历。最后得到有序数组。
快速排序是不稳定的算法，它不满足稳定算法的定义。
算法稳定性：假设在数列中存在a[i] = a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的。
快速排序时间复杂度
快速排序的时间复杂度在最坏的情况下是O(n^2)，平均时间复杂度是O(N*lgN)
这句话很好理解，假设被排序的数列中有N个数。遍历一次的时间复杂度是O(n)，需要遍历多少次那？至少lg(N+1)次，最多N次。
1、为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。因此，快速排序的遍历次数至少是lg(N+1)次。
2、为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快速排序的遍历次数最多是N次。
