public class QuickSort {
    //测试
    public static void main(String[] args) {

        QuickSort quickSort = new QuickSort();
        int[] ints = {3, 1, 7, 10, 6, 8, 2, -6, 123};

        int[] res = quickSort.quickSort(ints, 0, ints.length - 1);

        System.out.println("输出排序后的数组如下：");
        for (int i : res) {
            System.out.println(i);
        }

    }
   
/**
     * 快速排序算法主体
     *
     * @param arr
     * @param left 初始是0
     * @param right 初始是length-1
     * @return
     */
    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            // 获取基准值 base
　　　　　　　// 这个函数不仅仅选出了基准值，还修改了原来的数组　
            int base = partition(arr, left, right);
            //分别对左右两边递归调用
            quickSort(arr, left, base - 1);
            quickSort(arr, base + 1, right);
        }
        return arr;
    }

    /**
     * 选定基准值
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）int index = left + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[left]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr,left, index - 1);
        return index - 1;
    }

    /**
     * 交换数组中两个数
     *
     * @param arr
     * @param i
     * @param j
     */
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }