class Solution {
    // 原地排序 冒泡排序 选择排序 快速排序 插入排序
    // 快排 平均 O（nlogn） 最差O(n^2) 最好是O(nlogn)
    public void sortColors(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
    }
    public void quickSort(int[] nums, int low, int high) {
        if (low < high) {
            int index = partition(nums, low ,high);
            quickSort(nums, low ,index - 1);
            quickSort(nums, index + 1,high);
        }
    }
    public int partition(int[] nums, int low, int high) { // partition分区
        int pivot = nums[high];  // pivot基准
        int j = low;
        for (int i = low; i < high; i++) {
            if (nums[i] < pivot) {
                swap(nums, i, j);
                j++;
            }
        }
        swap(nums,j, high);
        return j;
    }
    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}