题解 | #最小的K个数#

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        quickSort(input,0,input.length-1,k);
        ArrayList<Integer> res=new ArrayList<>();
        for(int i=0;i<k;i++){
            res.add(input[i]);
        }
        return res;
    }
    void swap(int []arr,int i,int j){
        if(i!=j){
            arr[i]^=arr[j];
            arr[j]^=arr[i];
            arr[i]^=arr[j];
        }
    }
    void quickSort(int []arr ,int start,int end,int k){
        if(start<end){
            int key=arr[start];
            int i=start;
            for(int j=i+1;j<=end;j++){
                if(arr[j]<=key){
                    swap(arr,j,++i);
                }
                
            }
            arr[start]=arr[i];
            arr[i]=key;
            if(i>k){
            quickSort(arr,0,i-1,k);}
            else if(i<k)
            quickSort(arr,i+1,end,k);
            else 
                return;
        }
        
        return;
    }
}