最小的K个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

方法一：直接排序

直接对数组进行全排序，这种方式总是有效的，但是其实不用全部排序。

时间复杂度：O(nlongn)
空间复杂度：O(1)

方法二：堆排序

时间复杂度：O(nlongk), 插入容量为k的大根堆时间复杂度为O(longk), 一共遍历n个元素
空间复杂度：O(k)

方法二：快排

java">import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        int len = input.length;
        ArrayList<Integer> res = new ArrayList<>();
        if(input == null || len == 0 || k < 0 || k > len-1) return res;
        getK(input, k, 0, len-1);
        for(int i=0; i<k; i++){
            res.add(input[i]);
        }
        return res;
    }
    
    private static void getK(int[] arr, int k, int startIndex, int endIndex){
        int len = arr.length;
        if(arr == null || len == 0 || k > len || startIndex >= endIndex) return;
        int left = startIndex;
        int right = endIndex;
        int pivot = arr[left];
        
        while(left < right){
            while(left < right && arr[right] >= pivot) right--;
            arr[right] = arr[left];
            while(left < right && arr[left] <= pivot) left++;
            arr[left] = arr[right];
        }
        arr[left] = pivot;
        if(k == left) return;
        else if(k < left) getK(arr, k, startIndex, left-1);
        else getK(arr, k, left+1, endIndex);
    }
}

时间复杂度：平均时间复杂度为O(n)，每次partition的大小为n+n/2+n/4+... = 2n，最坏时间复杂度为O(n^2), 因为每次partition都只减少一个元素
空间复杂度：O(1)