package com.joe.print.mvp.ui.activity;

class aaa {

    public static void main(String[] age) {
        int[] arr = new int[]{4, 1, 8, 5, 3, 2, 9, 10, 6, 7};
        int[] brr = new int[]{5, 1, 2, 3, 8, 4, 9, 10, 6, 7};

        partition(arr, 0, 9);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ",");
        }
    }

    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        if (arr != null && arr.length > 0) {
            int start = startIndex, end = endIndex;
            int target = arr[startIndex];
            while (start < end) {

                while (start < end) {
                    if (arr[end] < target) {
                        swap(arr, start, end);
                        break;
                    } else {
                        end--;
                    }
                }

                while (start < end) {
                    if (arr[start] > target) {
                        swap(arr, start, end);
                        break;
                    } else {
                        start++;
                    }
                }
            }


        }
    }

    public static void swap(int[] arr, int index1, int index2) {
        int a = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = a;
    }

    //    public static int[] getLeastNumbers(int[] arr, int k) {
//        if (k == 0 || arr.length == 0) {
//            return new int[0];
//        }
//        // 最后一个参数表示我们要找的是下标为k-1的数
//        return quickSearch(arr, 0, arr.length - 1, k - 1);
//    }
//
//    private static int[] quickSearch(int[] nums, int lo, int hi, int k) {
//        // 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数；
//        int j = partition(nums, lo, hi);
//        if (j == k) {
//            return Arrays.copyOf(nums, j + 1);
//        }
//        // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
//        return j > k ? quickSearch(nums, lo, j - 1, k) : quickSearch(nums, j + 1, hi, k);
//    }
//
//    // 快排切分，返回下标j，使得比nums[j]小的数都在j的左边，比nums[j]大的数都在j的右边。
    private static void partition(int[] nums, int lo, int hi) {
        int k = nums[lo];
        int i = lo, j = hi + 1;
        while (true) {
            while (++i <= hi && nums[i] < k);
            while (--j >= lo && nums[j] > k);
            if (i >= j) {
                break;
            }
//            int t = nums[j];最近更新
//            nums[j] = nums[i];
//            nums[i] = t;
            swap(nums, i, j);
        }
        nums[lo] = nums[j];
        nums[j] = k;
        swap(nums, i, j);
    }

}