题解 | #最小的K个数#

快排

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(input == null || input.length == 0){
            return list;
        }
        quicksort(input,0,input.length -1);
        for(int i = 0;i < k ; i++){
            list.add(input[i]);
        }
        return list;
    }
    
    
    
    public static void quicksort(int[] arr,int L,int R){
        if(L>R){
            return ;
        }
        int left = L;
        int right = R;
        int pivot = arr[left];
        while(left <  right ){
        while(left < right && arr[right] >= pivot){
            right--;    
        }
        if(left < right){
            arr[left] = arr[right];
        }
        while(left<right && arr[left] <=pivot){
            left++;
        }
        if(left < right){
            arr[right] = arr[left];
        }
        if(left >= right){
            arr[left] = pivot;
        }    
        }
 
        
        quicksort(arr,L,right - 1);
        quicksort(arr,right + 1,R);
    }
}