public class Sort_QuickSort {

    public static void main(String[] args) {
        int[] nums = new int[]{6,9,1,4,8,2,5,7,6};
        Sort_QuickSort quickSort = new Sort_QuickSort();
        quickSort.quickSort(nums, 0, nums.length-1);
        for (int i=0;i< nums.length;i++) {
            System.out.print(nums[i] + " ");
        }
    }

    public void quickSort(int[] nums, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }
        int pivot = partition(nums, startIndex, endIndex);
        // pivot 左边的元素都比它小，右边的元素都比它大
        // 递归对 pivot 左半做相同的操作
        quickSort(nums, startIndex, pivot-1);
        // 递归对 pivot 右半做相同的操作
        quickSort(nums, pivot+1, endIndex);
    }


    private int partition(int[] nums, int startIndex, int endIndex) {
        // 最后要达到的效果是，pivot 左边的元素都比它小，右边的元素都比它大
        // 选取数组的第一个元素作为基准元素 pivot
        int pivotIndex = startIndex;
        int pivot = nums[pivotIndex];
        // 左右指针
        int left = startIndex;
        int right = endIndex;
        while (true) {
            // 在右边 找到第一个小于 pivot 的
            while (nums[right] >= pivot && left < right) {
                right--;
            }
            // 在左边找到第一个大于 pivot 的
            while (nums[left] <= pivot && left < right) {
                left++;
            }
            if (left < right) {
                // 交换左右两边
                swap(nums, left, right);
            }
            else {
                // 退出循环
                break;
            }
        }
        // 把最后的位置和 pivot 的位置交换
        swap(nums, left, pivotIndex);
        // 返回最后的位置（现在放的是pivot）
        return left;
    }

    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}