快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
基本思想
先从数组中找出一个数作为基准数
分区过程，将比这个数小的数全部放到它的左边，大于它的数全部放到右边
再对左右区间重复第二步，直到各区间都只有一个数
排序过程
在一篇博客上看到一个很有趣的讲解方法：叫做 挖坑填数+分治法。
假如有一个10个数的数组：i=0,j=9,pivot=array[i]=x
由于已经array[0]中的数保存到pivot中，可以理解成在数组array[0]上挖了个坑，可以将其他数据填充到这里来。
然后j向前找比当前基准数pivot小的数，当符合条件时(比如是第8个参数)，那么将array[8]挖出填充到array[0]这个坑。这时就多出了array[8]这个坑，于是从i开始向后找大于pivot的数，填充array[8]这个坑。
重复操作。
最后i==j时会退出循环，这时多出了array[i]这个坑，怎么办呢？将pivot填充到array[i]。这时对左右两个区间继续进行排序就好了。
算法实现
/** * 快速排序 */ public class QuickSort { public void sort(int[] array) { quickSort(array, 0, array.length - 1); } /** * 通过划分，基于分治思想，递归执行子任务排序最后合并 * @param low 数组首位索引 * @param high 数组末尾索引 */ private void quickSort(int[] array, int low, int high) { int pivotPos; if (low < high) { pivotPos = partition(array, low, high); quickSort(array, low, pivotPos - 1); quickSort(array, pivotPos + 1, high); } } /** * 简单划分方法 */ private int partition(int[] array, int i, int j) { int pivot = array[i]; // array[i] 就是 第一个坑 while (i < j) { while (i < j && array[j] >= pivot) { j--; // 从右向左找出小于基准数pivot的数来填充array[i] } if (i < j) { array[i] = array[j]; // 将array[j]填充到array[i]中，array[j]就形成了一个新的坑 i++; } while (i < j && array[i] <= pivot) { i++; // 从左向右找出大于基准数pivot的数来填充array[j] } if (i < j) { array[j] = array[i]; // 将array[i]填充到array[j]中，array[i]就形成了一个新的坑 j--; } } array[i] = pivot; // 退出时，i等于j。将pivot填到这个坑中。 return i; } }