快速排序采用的思想是分而治之。
1）将一整个大的无序序数组，根据数组中的某一个值，将数组分成两部分，一部分比这个值小，一部分比这个值大。
2）然后再对这两部分各自进行同样的操作，而当每一部分都有序之后，整个数组也就有序了。
从第二点，我们很明显可以想到递归，那么关键点就是前面怎么分这个数组了。
比较经典的分法有两种，今天就先说最常用的一种，首先看下面这一个图：
1）首先要有两个指针，一个从最前面开始，一个从最后面开始。
2）将数组中第一个元素拿出来，作为一个基准数来比较，比它大的，扔到后面，比它小的扔前面。而由于将它拿出来了，它原先所处的位置就空出来了，如图上的11。
3）从数组后面开始往前扫描，拿值与基准数比较，如果比基准数小，则将它放到数组中空出来的位置，也就是 i 当前的位置了。如图中，第一个 j 的值就是10，比基准数11，则将它放到a[i]，此时 i 的值是0，而a[i]是空出来的位置，那么 i 被放了，我们就要把 i 的指针往前移一位，而由于 j 的值被放到前面去了，此时 j 的位置就空出来了。
4）反过来，从 i 的位置从前开始往后扫，扫到 i = 2的时候，发现a[i] 是 12，比11大，那么就要把 12放到a[j]中，如上面第2步所示，而当j的位置被放了值了，那么j 就要往前移一位，而此时i的位置又空出来了，我们就可以重复第 3) 步的操作，再从后往前扫。
5）到最后，我们发现i 跟 j 相遇了，那么说明 j 后面的数都比基准数大，而i 前面的数都比基准数小了，那么最后就把基准数11 重新放到这个空出来的位置。
6）可以发现，这样一趟下来，这个数组就变成以11为界的左小右大的数组了，在这里一拆，再对各个部分进行同样的操作，最终就是排序的结果了。
根据这样的思路，我们也就可以写出如下代码了：
public static int partition(int[] a, int low, int high) {
int i = low;
int j = high;
int tmp = a[low];
while (i < j) {
while (i < j && a[j] >= tmp) {
j--;
}
if (i < j) {
a[i] = a[j];
i++;
}
while (i < j && a[i] <= tmp) {
i++;
}
if (i < j) {
a[j] = a[i];
j--;
}
}
a[i] = tmp;
return i;
} public static void quickSort(int[] a, int low, int high){
if(low < high){
int mid = partition(a, low, high);
quickSort(a, low, mid - 1);
quickSort(a, mid + 1, high);
}
}接下来我们来验证一下这种写法的正确性：
public static void main(String[] args) {
int[] a = { 11, 9, 12, 7, 4, 57, 44, 23, 10 };
printA(a);
quickSort(a, 0, a.length - 1);
printA(a);Before: 11 9 12 7 4 57 44 23 10
round 1 : 10 9 4 7 11 57 44 23 12
round 2 : 7 9 4 10 11 57 44 23 12
round 3 : 4 7 9 10 11 57 44 23 12
round 4 : 4 7 9 10 11 12 44 23 57
round 5 : 4 7 9 10 11 12 44 23 57
round 6 : 4 7 9 10 11 12 23 44 57
After: 4 7 9 10 11 12 23 44 57
这个对几个数进行比较，那如果我们对很多数呢，也来试一下吧，看看它是不是真的那么快速呢？
我们生成2千万个数，每个数都在1亿以内，如下：
int[] a = Helper.generateRandomNumbers(20000000, 100000000);
long start = System.currentTimeMillis();
quickSort(a, 0, a.length - 1);
long end = System.currentTimeMillis();
long duration = end - start;
Helper.print("duration = " + duration + "\n");duration = 3753Exception in thread "main" java.lang.StackOverflowError
at com.lms.QuickSort.quickSort(QuickSort.java:48)
at com.lms.QuickSort.quickSort(QuickSort.java:50)
at com.lms.QuickSort.quickSort(QuickSort.java:50)
at com.lms.QuickSort.quickSort(QuickSort.java:50)
at com.lms.QuickSort.quickSort(QuickSort.java:50)这说明采用递归来干活，还是要想想会不会栈压得太深，导致栈溢出。那么，我们就要想想非递归应该怎么做了。
其实递归也就是压栈出栈，那么我们就拿栈来实现不就好了吗？
public static void quickSort3(int[] a, int low , int high){
Stack<Integer> stack = new Stack<Integer>();
stack.push(low);
stack.push(high);
int i,j;
while(!stack.isEmpty()){
j = stack.pop();
i = stack.pop();
if(j < i) break;
int mid = partition2(a, i, j);
if(mid - 1 > i){
stack.push(i);
stack.push(mid - 1);
}
if(mid + 1 < j){
stack.push(mid + 1);
stack.push(j);
}
}
} int[] a = { 11, 9, 12, 7, 4, 57, 44, 23, 10 };
Helper.print("Before: ");printA(a);
quickSort3(a, 0, a.length - 1);
Helper.print("After: ");printA(a);Before: 11 9 12 7 4 57 44 23 10
After: 4 7 9 10 11 12 23 44 57
public static void main(String[] args) {
int[] a = Helper.generateRandomNumbers(20000000, 100000000);
long start = System.currentTimeMillis();
quickSort3(a, 0, a.length - 1);
long end = System.currentTimeMillis();
long duration = end - start;
Helper.print("duration = " + duration + "\n");
duration = 10343然后再手贱一下，对有序超大数组再排序，发现没溢出了，但是跑了好久好久。。。
有兴趣的童鞋还能够再看看下一章关于另一种经典的拆分函数: