算法奇妙屋(三)-快排分治

    public void sortColors(int[] nums) {
        int len = nums.length;
        int left = -1;
        int right = len;
        int i = 0;
        while (i < right) {
            if (nums[i] == 0) {
                swap(nums,++left,i++);
            }else if (nums[i] == 2) {
                swap(nums,--right,i);
            }else {
                i++;
            }
        }
    }
    public void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static int[] sortArray(int[] nums) {
        partition(nums,0,nums.length - 1);
        return nums;
    }
    static void partition(int[] nums,int start,int end) {
        if (start >= end) {
            return;
        }
        int len = nums.length;
        int tmp = nums[(new Random().nextInt(end - start + 1)) + start];
        int i = start;
        int left = start - 1;
        int right = end + 1;
        while (i < right) {
            if (nums[i] < tmp) {
                swap(nums,++left,i++);
            }else if (nums[i] > tmp) {
                swap(nums,--right,i);
            }else {
                i++;
            }
        }
        // [s,left], [left+1,right-1],[right,end]
        // 递归左面
        partition(nums,start,left);
        // 递归右面
        partition(nums,right,end);
    }
    static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static int findKthLargest(int[] nums, int k) {
        return partition( nums, 0, nums.length - 1,k);
    }

    static int partition(int[] nums, int start, int end,int k) {
        if (start == end) {
            return nums[start];
        }
        int key = nums[(new Random().nextInt(end - start + 1) + start)];
        int left = start - 1;
        int right = end + 1;
        int i = start;
        while (i < right) {
            if (nums[i] < key) {
                swap(nums,++left,i++);
            }else if (nums[i] > key) {
                swap(nums,--right,i);
            }else {
                i++;
            }
        }
        //[s,l] [l+1,r-1] [r,e]
        int b = right - 1 - (left +  1) + 1;
        int c = end - right + 1;
        if (k <= c) {
            return partition(nums,right,end,k);
        }else if (k <= b + c) {
            return key;
        }else {
            return partition(nums,start,left,k - b - c);
        }
    }

    static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
         partition(arr,0,arr.length - 1, k);

        for (int i = 0; i < k; i++) {
            ret[i] = arr[i];
        }
        return ret;
    }
    void partition(int[] arr, int s, int e, int k) {
        if (s >=e) {
            return;
        }
        int left = s - 1;
        int right = e + 1;
        int i = s;
        int key = arr[new Random().nextInt(e - s + 1) + s];
        while (i < right) {
            if (arr[i] < key) {
                swap(arr,++left,i++);
            }else if (arr[i] > key) {
                swap(arr, --right, i);
            }else {
                i++;
            }
        }
        int a = left - s + 1;
        int b = right - 1 - (left + 1) + 1;
        if (k < a) {
             partition(arr,s,left,k);
        }else if (k <= a + b) {
            return;
        }else {
             partition(arr,right,e,k - a - b);
        }
    }
    void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }