public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {8, 3, 5, 9, 2, 6, 4, 11, 15, 7, 1, 12};
        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    void quickSort(int[] arr, int left, int right) {
        int pivotPos = findPivotPosition(arr, left, right);
        if (left < right) {
            if (pivotPos > left) {
                quickSort(arr, left, pivotPos - 1);
            }
            if (pivotPos < right) {
                quickSort(arr, pivotPos + 1, right);
            }
        }
    }

    private int findPivotPosition(int[] arr, int left, int right) {
        if (left > right) {
            throw new RuntimeException("left > right");
        }
        if (left == right) {
            return left;
        }
        int pivot = arr[left];
        //i：左侧位置，j：右侧位置
        int i = left, j = right;
        for (; i < j; ) {
            //移动右侧，小于pivot时，移到左侧，再让左侧移动，当i=j时，说明已经找到了pivote的正确位置：左边的都比pivote小，右侧的都比pivote大
            //查找范围[i, j]
            for (; j > i; ) {
                if (arr[j] < pivot) {
                    arr[i] = arr[j];
                    break;
                }
                j--;
            }
            if (i == j) {
                arr[i] = pivot;
                return i;
            }
            for (; i < j; ) {
                if (arr[i] > pivot) {
                    arr[j] = arr[i];
                    break;
                }
                i++;
            }
            if (i == j) {
                arr[i] = pivot;
                return i;
            }
        }

        return i;
    }

}