题目描述：力扣

思路：快速排序的变形，不需要完全排序

由partition函数返回的下标将数组分成2部分，前边大于等于下标元素，后边小于等于下标元素，

当该下标等于K-1时（因为数组下标是从0开始的，所以是K-1），直接返回数组的前K个元素；

当返回的下标大于K-1时，只需要对下标前部分进行排序，后部分元素不需要；

当返回的下标小于K-1时，需要对后部分进行排序，前面的不需要；

在Partition函数中需要注意的是以第一个元素为基准时，先进行的是从后往前遍历，找到小于基准值的元素，将其值赋给low指向的位置，再进行从前向后的遍历，找到大于基准值的元素，将其值赋给high指向的元素。 

class Solution {
    public  int[] getLeastNumbers(int[] arr, int k) {
        if(arr.length==0 || k == 0)
            return new int[]{};
		return quickSort(arr, 0, arr.length-1, k-1);
    }
	
	public int[] quickSort(int[] arr , int low , int high, int k){
		int i = partition(arr,low,high);
		if(i==k){
			return Arrays.copyOf(arr,i+1);
		}
		if(i>k){
			return quickSort(arr, low, i-1,k);
		}
		else{
			return quickSort(arr , i+1, high ,k);
		}
	}
	public int partition(int[] arr, int low, int high){
		int base = arr[low];
		while(high>low){
			while(high > low && arr[high]>=base){
				high--;
			}
            arr[low]=arr[high];
            while(high > low && arr[low]<=base){
				low++;
			}
            arr[high]=arr[low];
		}
		arr[low]=base;
		return low;
	}

}