一.概述
快速排序是对冒泡排序的一种改进。
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
二.原理
1.首先设定一个分界值（默认为第一个数），通过该分界值将数组分成左右两部分；
2.将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值；
3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4.重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。
具体的切分过程：
1.找一个基准值（默认为第一个元素），用两个指针分别指向数组的头部和尾部；
2.先从右向左开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；
3.再从左向右开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；
4.交换当前左边指针位置和右边指针位置的元素；
5.重复2,3,4步骤，直到左边指针的值大于右边指针的值停止。
例：
设定基准值，并准备两个指针，left指针指向分界值所在的索引lo处，right指针指向hi+1。
思路：right指针从右往左走，找到比6小的元素；然后left从左往右走，找到比6大的元素（双向排查），而后两数交换。
第一次，right指针左移一位，指向8，8>6，不满足。再左移来到5，5<6，满足，指针暂停在5处。
同理，left指针右移，寻找比6大的元素，依次移到 1 2 都不满足，直到指向7，7>6，满足条件。
交换right指针指向的“5”和left指针指向的“7”。
将两个指针指向的元素交换之后，right指针继续左移找到4<6，然后left左移找到9>6，交换4和9。
Again，right指针左移找到3<6，指针停在3。left指针右移到3也就是right指针的位置，此时满足条件 (left>=right) ，left和right指针重合，即代表此时两个指针扫描完毕，这时交换分界值6 和两个指针共同指向的值3。
到此这一数组的切分完成，然后以分界值为界，将其分为两个数组，再重复以上步骤。
三.Java代码实现
public class quick {
public static void sort(int[] a){
int lo=0;
int hi=a.length-1;
sort(a,lo,hi);
}
public static void sort(int[]a,int lo,int hi){
if(lo>=hi){//安全校验，即递归出口
return;
}
int partition=partition(a,lo,hi); //返回分界值交换后的索引(最后的right值)
//按照分界值继续递归切分
sort(a,lo,partition-1);
sort(a,partition+1,hi);
}
private static int partition(int[] a, int lo, int hi) {
//确定分界值
int key=a[lo];
//定义两个指针，分别指向带切分数组的最小索引处和最大索引处下一位
int left=lo;
int right=hi+1;
//切分
while(true) {
//先右
while (a[--right]>key) {//找的是right < key ，循环条件相反。
if(right==lo){
break;}
}
//后左
while(a[++left]<key){ //找的是left>key，循环条件相反
if(left==hi){
break;
}
}
//左右指针重合，即排查完毕，跳出最外层循环
if(left>=right){
break;
}else{
swap(a,left,right);//指针还未重合，则交换左、右指针处元素
}
}
swap(a,lo,right);//最后交换分界值和重合处元素
return right;//返回分界值交换后的索引
}
public static void swap(int[] a,int lo,int hi){
int k=a[lo];
a[lo]=a[hi];
a[hi]=k;
}
public static void main(String[] args) {
int[]a={6, 1, 2, 7, 9, 3, 4, 5, 8};
sort(a);
System.out.println(Arrays.toString(a));
}
}
运行结果：
[1, 2, 3, 4, 5, 6, 7, 8, 9]
需要注意的地方：
- 快速排序是先切分并返回一个分界值的索引int值，再进行递归； 而归并排序是先递归，再进行再调用merge方法进行归并。
- 快速和归并两种排序的递归出口相同，都是
if(lo>=hi){ return;} - 判断左右指针是否重合的条件必须是
if(left>=right){ break;}
而不能是if(left==right){ break;} 。
以第一轮切分为例，分界值key元素=6，经过两次交换后，
数组序列为 {6，1，2，5，4，3，9，7，8 }，
当right索引=5指向“3”并停下时，left索引来到4指向“4”，不满足条件，继续left指针的while循环：
while(a[++left]<key){
if(left==hi){
break;
}
}
运行++left，left来到5指向元素3，此时right指针和left指针都是5，理应停下，但是！left循环的跳出条件是找到比分界值key大的元素或者left到达hi数组边界，所以此时不会跳出循环！
再次运行++left，left=6指向元素9，此时满足条件9>key，跳出left的while循环。此时代码才会运行到if(left>=right){ break; 而此时right指针为5，left为6，left已经超过了right，而判断指针重合的代码块：
if(left==right){
break;
}else{
swap(a,left,right);
并没有起作用，该轮切分不会return，且left会继续++，所以判断指针重合的条件必须是if(left>=right){ break;。