题解 | #最小的K个数#

import java.util.ArrayList;

public class Solution {
    ArrayList<Integer> arrayList = new ArrayList();
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if(input.length>0){
        //先快排，再获取值
        qsort(input,0,input.length-1);
        for(int i2= 0;i2<k;i2++)
            {
                arrayList.add(input[i2]); 
            }
            return arrayList;}
        else{
            return arrayList;
        }
    }
public void qsort(int []a,int l,int r){
        int mid = a[l];
        int left = l;
        int right = r;
        int temp =0;
        int i=0;
        while(left<right){
             //右边找到比a[l]小的第一个数;和a[l]相等的数不移动，比mid大的数不断后移
             //先right--能确保left和right相等时a[left]<=a[mid],上一轮已经比较替换
            while(a[right]>=mid&&left<right){
                right--;
            }
            //左边找到比a[l]大的第一个数;和a[l]相等的数不移动，比mid小的数不断前移
            while(a[left]<=mid&&left<right){
                left++;
            }
            temp = a[left];
            a[left] = a[right];
            a[right] = temp;
               
        }
        //最左边的数a[l]和a[left]替换，一次递归只确定一个数a[l]的位置
        temp = a[left];
        a[left] = a[l];
        a[l] = temp;

        if(left>l){
            qsort(a,l,left-1);
        }
        if(right<r){
            qsort(a,right+1,r);
        }
    }
}