快排变形-最小的k个数

题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
解题思路
利用快速排序的思路-以第一个元素为界，将比它小的放在它的左侧，将比它大的，放在它的右侧
而我们是要最小的k个数，并不要求这k个数的顺序
则依次进行快速排序
根据示例可知，以4为关键元素，得出前3个比4小，后4个比4大。
如果k==3或者k==4，则直接输出input的前k个元素就好
如果k<3,则对前半段再进行快排，还是找前k个元素
如果k>4,则对后半段再进行快排，寻找前k-4个元素（因为前边4个已经出来了）
java代码实现如下： 15ms 9924KB

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> ans=new ArrayList<>();
        if(k>input.length || k==0){
            return ans;
        }
        get(input,0,input.length,k);
        for(int i=0;i<k;i++){
            ans.add(input[i]);
        }
        return ans;
    }
    public void get(int[] input,int p,int r,int k){
        int q=getindex(input,p,r);
        System.out.println(q);
        for(int i=0;i<input.length;i++){
            System.out.print(input[i]+"  ");
        }
        System.out.println();
        if(k<q){
            get(input,0,q,k);
        }
        else if(k>q+1){
            get(input,q+1,input.length,k-q-1);
        }
    }
    public int getindex(int[] input,int p,int r){
        int i=p;
        int j=r;
        int key=input[i];
        while(true){
            while(input[++i]<key && i<j);
            while(input[--j]>=key);
            if(i>=j) break;
            int tmp=input[i];
            input[i]=input[j];
            input[j]=tmp;
        }
        input[p]=input[j];
        input[j]=key;
        return j;
    }
}