快速排序的重点就在于第二步，我们如何能将区间分成三部分。一般我们有三种方法来分组，分别是Hover法、挖坑法、前后下标法，下面来一一介绍。 Hover法：就是分别用两个下标索引begin、end指向数组的第一个元素和最后一个元素，从begin开始与基准值比较，begin下标处的元素要是小于基准值，begin下标++，往后走，当走到的位置的数大于基准值时，begin停下来，此时end从最后面往前走，若是end处的元素大于基准值，则end- -往前走，若是走到了所在元素大于基准值时，end停下来。此时begin和end都遇到了瓶颈走不动了，我们只需要交换begin和end处的元素即可继续进行，直到begin和end相遇为止，此时即是基准值应该处的位置，我们交换begin（或end）下标处的元素和基准值即可。 挖坑法：挖坑法首先将区间最后边的基准值保存起来，此处就像形成了一个坑，和Hover法一样，也是用两个下标索引begin和end，分别放在数组最左边和最右边。从begin开始和基准值比较，如果小于基准值，begin++往前走，若是大于基准值，则将该值放入坑中，此时begin处就变成了一个坑，再从end开始，end往前走，若是大于基准值则end- -往前走，若是小于基准值，则将end处的值填在begin处的坑中，重复上述步骤，直到begin和end相遇，相遇处即是基准值所应该在的地方。将基准值填在这里即可。 前后坐标法：前后坐标法是用了两个下标索引div和i，这两个索引都在left处，将i处的值与基准值进行比较，当该值小于等于基准值时，交换div和i处的值，div和i同时++向后走，如果坐标为i处的值大于基准值时，只让i++向后走，当i遍历完时，div所在的位置就是基准值的位置。 此处只是对将数组分成三部分做了文字描述，推荐这篇文章，作者利用动画将快速排序讲的更为细致。快速排序优秀文章
快速排序代码如下：
public class Test { // 交换两个数 private static void swap(int[] array, int x, int y){ int temp = array[x]; array[x] = array[y]; array[y] = temp; } // 快速排序--升序 // Hover法 private static int partion(int[] array, int left, int right){ int begin = left; int end = right; while(begin < end){ while(begin < end && array[begin] <= array[right]){ begin++; } while(begin< end && array[end] >= array[right]){ end--; } swap(array,begin,end); } swap(array,begin,right); return begin; } // 挖坑法 private static int partion1(int[] array,int left,int right){ int begin = left; int end = right; int pivort = array[right]; while(begin < end){ while(begin < end && array[begin] <= pivort){ begin++; } array[end] = array[begin]; while(begin < end && array[right] >= pivort){ end--; } array[begin] = array[end]; } array[begin] = pivort; return begin; } // 前后下标法 private static int partion2(int[] array,int left,int right){ int div = left; int i = left; while(i < right){ if(array[i] > array[right]){ swap(array,div,i); div++; i++; }else{ i++; } } swap(array,div,right); return div; } public static void quickSort(int[] array,int left,int right){ // size == 1 if(left == right){ return; } // size == 0 if(left < right){ return; } int stand = partion(array,left,right); quickSort(array,0,stand-1); quickSort(array,stand+1,right); } private static void quick(int[] array) { if(array.length>0){ quickSort(array,0,array.length-1); } } public static void main(String[] args) { int[] array = {9,5,-1,10,0,2,7,3,8,6}; // selectSort(array); quick(array); for(int i = 0; i < array.length; i++){ System.out.print(array[i]+"、"); } } } 堆排序：由于选择排序在遍历过程中，会进行多次重复的比较，因此我们可以采用堆排序来解决这种问题。首先我们把数组建成一个大堆，再对这个大堆做向下调整，向下调整的前提是该堆中只有一个位置不满足堆的性质，其余位置都满足堆的性质了。向下调整分为三步： ① 我们首先需要判断传进来的下标是不是叶子节点 ② 找出该节点的孩子中较大的那一个孩子 ③ 比较较大的孩子和父节点的大小，若是孩子节点大，则交换，然后继续做向下调整 代码如下： public static void heapSort(int[] array) { for (int i = 0; i < array.length; i++) { createMaxHeap(array, array.length - 1 - i); swap(array, 0, array.length-1-i); } } public static void createMaxHeap(int[] data, int lastIndex) { // 从lastIndex处节点（最后一个节点）的父节点开始 for (int i = (lastIndex-1)/2; i >= 0; i--) { int k = i; while (2 * k + 1 <= lastIndex) { int biggerIndex = 2 * k + 1; if (biggerIndex + 1 <= lastIndex) { if (data[biggerIndex] < data[biggerIndex + 1]) { biggerIndex++; } } if (data[k] < data[biggerIndex]) { swap(data, k, biggerIndex); k = biggerIndex; } else { break; } } } }