快速排序

/**
     * 快速排序
     */
    public static void quickSort(int [] arr, int left, int right){
        if(left < right){
            int index = partition(arr, left, right);
            // 对基准值两边的元素再继续进行分别处理
            quickSort(arr, left, index - 1);
            quickSort(arr, index + 1, right);
        }
    }

    /**
     * 默认获取第一个元素为基准值，返回基准值的位置下标
     */
    public static int partition(int [] arr, int left, int right){
        // 选择区间内第一个元素作为基准值
        int baseValue = arr[left];
        int index = left + 1;
        for (int i = index; i <= right; i++) {
            // 把所有小于基准值的元素从左依次放好
            if(arr[i] < baseValue){
                // 交换元素位置
                int temp = arr[i];
                arr[i] = arr[index];
                arr[index] = temp;
                index++;
            }
        }

        // 为什么要减一，因为这个index-1这个位置的元素是小于基准值的
        // 如果碰到特殊情况怎么办？比如arr[left]恰好是最小的一个元素，此时index-1刚好是left，所以也不影响最终结果
        index--;

        // 把基准值放到中间去
        // 和left上的元素（也就是基准值）交换位置以后，恰好left-right区间内，基准值左边的都小于它，右边的元素都大于它
        arr[left] = arr[index];
        arr[index] = baseValue;

        // 返回基准值的位置下标
        return index;
    }