2021-07-21 最小的K个数

就是用快排，在快排的时候如果超过k，后面的就不进行排序

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        // 快排简化
        quickSort(input,0,input.length-1,k);
        
        ArrayList list = new ArrayList();
        for(int i = 0;i<k;i++){
            list.add(input[i]);
        }
        return list;
    }
    //右边的是数组最后一个的下表
    private void quickSort(int[] nums,int start,int end,int k){
        try {
            if(start>=end){
                return;
            }
            if(start+1 == end){
                if(nums[start]>nums[end]){
                    swap(nums,start,end);
                }
                return;
            }
            int mid = nums[start];
            List<Integer> left = new ArrayList<>();
            List<Integer> right = new ArrayList<>();
            for (int i = start+1; i <= end; i++) {
                if(nums[i]< mid){
                    left.add(nums[i]);
                }
                else {
                    right.add(nums[i]);
                }
            }
            int midNum = start+left.size();
            
            int index = start;
            for (int i = 0; i < left.size(); i++) {
                nums[index] = left.get(i);
                index++;
            }
            nums[index] = mid;
            index++;
            for (int i = 0; i < right.size(); i++) {
                nums[index] = right.get(i);
                index++;
            }
            quickSort(nums,start,midNum,k);
            if (midNum <= k) {
                quickSort(nums, midNum + 1, end,k);
            }
        } catch (Error e) {
            System.out.println("Exce:"+start +"  "+ end);
        }
    }
    
    public void swap(int[] nums,int left,int right){
        int temp = left;
        left = right;
        right = temp;
    }