快速排序排序效率在同为O(N*logN)的几种排序方法中效率较高。
该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
虽然快速排序称为分治法，但分治法这三个字显然无法很好的概括快速排序的全部步骤。快速排序又有一个形象的表达：挖坑填数+分治法（代码如下）：
class QuickSort { public static void main(String[] args) { int[] array = { 18, 13, 7, 6, 21, 14, 32, 2, 1}; queckSort(array,0,array.length-1); for(int i = 0 ; i < array.length ; i++){ System.out.print(array[i]+" "); } } //分治递归 public static void queckSort(int[] array , int start , int end){ if(start >= end){ return; }else{ int mid = partition(array, start, end); queckSort(array, start, mid); queckSort(array, mid + 1, end); } } public static int partition(int[] array , int start , int end ){ //挖第一个坑，把坑里的数取出来存在mid中 int mid = array[start]; while(start < end){ //如何右边的数大于mid，则往左边移动 while(array[end]>=mid && end>start){ end--; } /* 跳出上面的循环说明右边有一个小于mid的数， 把这个数填到左边的坑里,(array[start]一开始赋值给了mid，挖了一个坑), 并在右边留下一个坑array[end] */ array[start] = array[end]; //如何左边的数小于mid，则往左边移动 while(array[start]<=mid && end>start){ start++; } /* 跳出上面的循环说明左边有一个大于mid的数， 把这个数填到右边的坑里(array[end]是上一步array[start] = array[end]挖的坑) 并在左边留下一个坑array[start] */ array[end] = array[start]; } //最后把mid填到剩下的一个坑里 array[start] = mid; //返回这个坑的下标 return start; } }对挖坑填数进行总结
1．将基准数挖出形成第一个坑a[start]，基准数存在mid中。
2．end–由后向前找比它小的数，找到后挖出此数填前一个坑a[start]中。
3．start++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[end]中。
4．再重复执行2，3二步，直到start==end，将mid中的基准数填入a[start]中。
