快速排序-维基百科

一次快排分区的结果

class QuickSort {

    private int[] mArray;

    public QuickSort(int[] array) {
        this.mArray = array;
    }

    private void swap(int from, int to) {
        int t = mArray[from];
        mArray[from] = mArray[to];
        mArray[to] = t;
    }

    /**
     * 分区(原地版本)
     *
     * @param left  数组左侧
     * @param right 数组末尾
     * @return 分区下标
     */
    private int partition(int left, int right) {
        //选择左则作为分区基准值
        int pivotValue = mArray[left];
        //将基准移到尾部
        swap(left, right);
        int storeIndex = left;
        for (int i = left; i < right; i++) {
            if (mArray[i] <= pivotValue) {
                swap(storeIndex, i);
                storeIndex++;
            }
        }
        //将基准移到分区位置
        swap(right, storeIndex);
        return storeIndex;
    }

	/*
    * 分区(基础版本)
    * 以每次分区left元素为标志
    */
private int partition(int left, int right) {
        int key = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= key) {
                right--;
            }
            if (left < right)
                arr[left] = arr[right];
            while (left < right && arr[left] < key) {
                left++;
            }
            if (left < right)
                arr[right] = arr[left];
        }
        arr[left] = key;
        return left;
    }

    public void sort(int left, int right) {
        if (right > left) {
            //进行分区，返回分区下标
            int pivotNewIndex = partition(left, right);
            sort(left, pivotNewIndex - 1);
            sort(pivotNewIndex + 1, right);
        }
    }
}