快速排序思想

对数组[l,r]进行快排切分后得到基准值的索引p，由此有三个区间[l, p), p, [p+1, r)。[l,p)为小于等于p的值
[p+1,r)为大于等于p的值。

1. 若p==k-1，则说明在p之前的数就是前k大的数；
2. 若p<k-1，则说明第k大的在p右边[p+1,r]；
3. 若p>k-1，则答案在左边[l,p]。

import java.util.*;
public class Solution {

    int partition(int [] input ,int left,int right){
        int pivot = input[left];
        while(left<right){
            while(left<right&&input[right]>=pivot)
                right--;
            input[left]=input[right];
            while(left<right&&input[left]<=pivot)
                left++;
            input[right]=input[left];
        }
        input[left] = pivot;
        return left;
    }

    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
       ArrayList<Integer> list =new ArrayList();
       if(input.length==0||k>input.length)
           return list;
       int i=0,j=input.length-1;
        while(i<j){
            //切分
            int p  = partition(input,i,j);
            //当找到第k大的数，p+1==j是因为第k大的数可能在最后
            if(p==k-1||p+1==j){
                for(int x=0;x<k;x++)
                    list.add(input[x]);
                return list;
            }
            //当前的数在第k大的左边
            else if(p<k){
                i=p+1;
            }
            //第k大的在当前的数的左边
            else
                j=p;

        }
        return list;
    }
}