快排是最基础的几个排序算法之一，今天再来回顾下

public class QuickSort {

    public static void quickSort(int[] array){
        if(array != null){
            quickSort(array, 0, array.length-1);
        }
    }

    private static void quickSort(int[] array,int beg,int end){
        if(beg >= end || array == null)
            return;
        int p = partition(array, beg, end);
        quickSort(array, beg, p-1);
        quickSort(array, p+1, end);
    }
}

上面就是快排主要的框架，最重要就是partition方法，它是划分并找到下次分割排序的位置p

常用的partition方法

private static int partition(int[] array, int beg, int end) {
        int first = array[beg];
        int i = beg, j = end;
        while (i < j) {
            while (array[i] <= first && i < end) {
                i++;
            }
            while (array[j] > first && j >= beg) {
                j--;
            }
            if (i < j) {
                array[i] = array[i] ^ array[j];
                array[j] = array[i] ^ array[j];
                array[i] = array[i] ^ array[j];
            }
        }
        if (j != beg) {
            array[j] = array[beg] ^ array[j];
            array[beg] = array[beg] ^ array[j];
            array[j] = array[beg] ^ array[j];
        }
        return j;
    }

第二种partition方法实现

private static int partition(int[] array,int beg,int end){
        int last = array[end];
        int i = beg -1;
        for (int j = beg; j <= end-1; j++) {
            if(array[j] <= last){
                i++;
                if(i != j){
                    array[i] = array[i]^array[j];
                    array[j] = array[i]^array[j];
                    array[i] = array[i]^array[j];
                }
            }
        }
        if((i+1) != end){
            array[i+1] = array[i+1]^array[end];
            array[end] = array[i+1]^array[end];
            array[i+1] = array[i+1]^array[end];
        }
        return i+1;
    }

个人比较喜欢第二种写法，比较简洁

<div>
    作者：qarkly112649 发表于2014/6/29 17:24:20 [原文链接](http://blog.csdn.net/qarkly112649/article/details/35794097)
</div>
<div>
阅读：2000 评论：0 [查看评论](http://blog.csdn.net/qarkly112649/article/details/35794097#comments)
</div>