快排中核心的方法应该算是Partition函数了，它的作用就是将整个数组分成小于基准值的左边，和大于基准值的右边。

普通的Partition函数是这样的：

public static int partition1(int[] array,int lo,int hi){

        //以第一个值为基准值，当然你也可以3取1，

        int key=array[lo];

        while(lo<hi){

            while(array[hi]>key&&hi>lo){//从后半部分向前扫描

                hi--;

            }

            array[lo]=array[hi];

            while(array[lo]<=key&&hi>lo){//从前半部分向后扫描

                lo++;

            }

            array[hi]=array[lo];

        }

        array[hi]=key;

        return hi;

    }

public static void main(String[] args) {

        int[] a = {34,2,25,1,12,34,12,56,23,15,34,67,89,54,34};

        partition2(a, 0, 14);

        for(int i=0; i<a.length; i++) {

            System.err.print(a[i]+" ");

        }

    }

打印的结果是：

34 2 25 1 12 34 12 34 23 15 **34** 67 89 54 56 

看出来没，大家都是相同的基准值34是各自分开的，我们希望得结果应该是这样的：

25 1 12 12 23 15 34 34 34 34 89 54 67 56

这样的好处是相同的值，在后续的遍历过程中，不用再比较一次了。

（左程云，左神写的）

牛逼的Partition函数是这样的：

public static int[] partition1(int[] arr, int begin, int end, int pivotValue) {

        int small = begin - 1;

        int cur = begin;

        int big = end + 1;

        while (cur != big) {

            if (arr[cur] < pivotValue) {

                swap(arr, ++small, cur++);

            } else if (arr[cur] > pivotValue) {

                swap(arr, cur, --big);

            } else {

                cur++;

            }

        }

        int[] range = new int[2];

        range[0] = small + 1;

        range[1] = big - 1;

        return range;

    }

public static void main(String[] args) {

        int[] a = {34,2,25,1,12,34,12,56,23,15,34,67,89,54,34};

        int[] b = partition1(a,0,14,34);

        System.out.println(b[0]);

        System.out.println(b[1]);

        for(int i=0; i<a.length; i++) {

            System.err.print(a[i]+" ");

        }

    }

输出的结果是：

7 //相同基准值的起始索引

10 //相同基准值的末尾索引

2 25 1 12 12 23 15 **34 34 34 34** 89 54 67 56 

这样，你下一次递归直接就可以避免重复比较相同的基准值了。