leetcode40：TOP k，快排算法

public void quickSearch(int[] arr, int lo, int hi){
        if (lo > hi) {
            return;
        }
        
        int start = lo;
        int end = hi + 1;
        int v = arr[lo];
        while (true) {
            while (--end >= lo && arr[end] > v);
            while (++start <= hi && arr[start] < v);
            if(start >= end){
                break;
            }
            int t = arr[end];
            arr[end] = arr[start];
            arr[start] = t;
        }

        arr[lo] = arr[end];
        arr[end] = v;
        
        quickSearch(arr, lo, end - 1);
        quickSearch(arr, end + 1, hi);
    }

class Solution4 {

    /**
     * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
     */
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k == 0 ||  arr.length < k){
            return new int[0];
        }
        return sort(arr, 0, arr.length - 1, k - 1);
    }

    public int[] sort(int[] arr, int lo, int hi, int k){
        // 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的
        int j = quickSort(arr, lo, hi);
        if(j == k) {
            return Arrays.copyOf(arr, j + 1);
        }

        // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
        return j > k ? sort(arr, lo, j - 1, k) : sort(arr, j + 1, hi, k);
    }

    public int quickSort(int[] arr, int lo, int hi){
        int i = lo;
        int j = hi + 1;
        // 假设临界的值
        int v = arr[lo];
        while(true) {
            while(--j >= lo && arr[j] > v);
            while(++i <= hi && arr[i] < v);
            if(i >= j) {
                break;
            }
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }

        // 将临界值和j所在位置进行替换
        arr[lo] = arr[j];
        arr[j] = v;
        return j;
    }