为什么叫快速排序，因为很快，并且空间复杂度是常数级别的，比归并排序好。
快速排序的基础是 一次划分。通过这一次划分把一个元素排定在合适的位置，即：该元素左边的元素都不大于它，右边都不小于它。可以等于。
借助一次划分，可以确定一个元素的位置。然后再将它左右两边的元素分别进行一次划分，当进行到单个元素的时候，整个数组就是有序的了。
回想之前的选择排序，也是一个个的确定元素的位置，为什么快速排序可以做到NlgN呢？
个人的感觉有两个方面：
1、通过划分，使得每次遍历的规模不断减小。第一次需要遍历整个数组才能确定一个元素的位置，通过划分之后。再对两个子数组进行遍历，可以排定两个元素的位置。但是遍历这两个数组的时间比选择排序遍历剩下的数组小得多。
2、通过划分，使得元素的大致位置已经确定了。例如第一次划分了k在中间，那么左端的元素，只可能在k的左端，而不需要考虑k右端的位置了。
一：一次划分
public static int partition(int a[],int lo,int hi){
int i = lo;
int j = hi+1;//为了j--
int temp = a[lo];//选第一个来切分，这个作为临时变量
while(true){
//先从左边开始，找到一个大于temp的
//再从右边开始，找到一个小于temp的
//交换
//++i,为了跳过比较原值i，如果小于就继续加
while(a[++i]<temp)
if(i == hi)
break;
//注意不能用j--
//--j和j--在没有到终止条件之前，没有区别
//但是在终止条件的时候，如果是j--，即使当前不符合条件，跳出循环之后，还会--，那么就左移了一位了，后面我们用j交换位置，会出错
while(temp<a[--j])
if(j == lo)
break;
//终止条件
//假如i=j，可以证明当前a[j]=temp
//假如i>j，没有必要继续执行下去了，因为i的增加条件是，a[i]<temp，后面都是大于temp的，因为j是这样移过来的
//假如i>j，a[lo]和a[j]交换后，temp=a[j]<a[i]，对的
if(i>=j)
break;
Example.exch(a, i, j);
}//end while
//将a[lo]放到合适的位置
//因为j是最后变化的，所以与j交换没错
Example.exch(a, lo, j);
return j;
}
二：快速排序
public static void sort(int a[]){
sort(a,0,a.length-1);
}
public static void sort(int[] a,int lo,int hi){
if(lo>=hi)
return;
int j = partition(a,lo,hi);
sort(a,lo,j-1);
sort(a,j+1,hi);//因为一次划分之后，a[j]的位置是确定的了，不用再划分
}
时间复杂度：
递归的次数lgN，划分一次不到N，所以大概是NlgN。
空间复杂度：
每次划分只用了一个临时变量，用于原地划分。总共有lgN次，所以空间复杂度是lgN
稳定性：
在上面可以看到，与划分值（最左端）相等的值，有可能被交换到它的左边，而划分值交换到中间，所以是不稳定的。