最小的k个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
O(n) , 基于快排思想，但是会修改原数组

public int partition(int [] input,int s,int e){
        int value = input[e];
        int i = s-1;
        int j = s;
        for(;j<e;j++){
            if(input[j]<value){
                i++;
                int temp = input[i];
                input[i] = input[j];
                input[j] = temp;
            }
        }
        input[e] = input[i+1];
        input[i+1] = value;
        return i+1;
    }
    
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
            ArrayList<Integer> list = new ArrayList<Integer>();    
            int len = input.length;
            int mid;
            int s=0,e=len-1;
            if(k<=0||k>len){
                return list;
            }
            while((k-1)!=(mid=partition(input,s,e))){
                if(mid>(k-1)){
                    e=mid-1;
                }else{
                    s=mid+1;
                }
            }
            for(int i=0;i<k;i++){
                list.add(input[i]);
            }
            return list;
            
    }

O(nlogk)，堆排序，建立k个元素的堆

public class Solution {
    public int maxHeap[];
    public int length;
    
    public void adjustHeap(int p){
        int child = p*2+1;
        int value = maxHeap[p];
        while(child<length){
            if((child+1)<length&&maxHeap[child+1]>maxHeap[child]){
                child++;
            }
            if(maxHeap[child]>value){
                maxHeap[p] = maxHeap[child];
                p=child;
                child=2*p+1;
            }else
                break;
        }
        maxHeap[p] = value;
    }
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if(k<=0||k>input.length){
            return new ArrayList<Integer>();
        }
        maxHeap= new int[k];
        length = k;
        for(int i=0;i<k;i++){
            maxHeap[i] = input[i];
        }
        for(int i=k/2-1;i>=0;i--){
            adjustHeap(i);
        }
        for(int i=k;i<input.length;i++){
            if(input[i]<maxHeap[0]){
                maxHeap[0] = input[i];
                adjustHeap(0);
            }
        }
        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i=0;i<length;i++){
            list.add(maxHeap[i]);
        }
        return list;
    }
}