数组中最小的k个数字【排序，最大堆，Quick Select算法

题目：

输入n个数，找出其中最小的k个数(k<=n)。

思路：

思路一：

将n个数排序，输出前k个。时间复杂度为O(nlogn)。当k比较大的时候（比如k>n/2），这种方法是一种不错的方法，但是在k比较小的时候，我们并不关心k位之后的数字的顺序，我们甚至也不关心前k个数字的顺序，这种方法带来了额外的操作，所以很显然时间上还有额外的优化空间。

思路二：

维护一个容量为k最大堆，将n个数入堆，最后堆中剩的k个数字就是最小的k个数。维护堆的时间复杂度为logk，需要将n个数字依次入堆，所以这种方法的时间复杂度为O(nlogk)。

思路三：

在方法二中，维护堆的过程依然可以得到前k个数字的顺序，而我们是不关心前k个数字的顺序的。用什么办法可以把数组分成两部分，而不关心每一部分的顺序呢？

当我们在进行快排的时候，我们每次会选择一个“哨兵”，小于哨兵的放在左边，大于哨兵的放在右边，那么如果哨兵的位置恰好为k，那不就刚好分好了吗？如果哨兵的位置不那么完美怎么办呢？递归进行下一次划分就好了！如果哨兵的位置>k，那么就递归处理左边的部分，否则处理右边的部分。

这种方法被称为“Quick Select”,与快排相比，快排需要每次递归处理两边的区间，而这种方法只处理一边，所以时间复杂度低于快排。利用主定理可以求出时间复杂度为O(n)，在不关心前k个数字顺序时是最高效的算法之一。

代码：

import java.util.*;

public class Solution {

    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

        ArrayList<Integer> ans = new ArrayList<>();

        if (k>input.length) {

        quickSelect(input,0,input.length-1,k-1);

        for (int i = 0;i<k;i++){

            ans.add(input[i]);

        }

        return ans;

    }

    public void quickSelect(int[] a,int l,int r,int k){

        if (l>=r) return;

        if (r == l+1){

            if (a[l]>a[r]){

                swap(a,l,r);

            }

            return;

        }

        int i = l;

        int j = r+1;

        int tmp = 0;

        while (i<j){

            i++;

            while (i<=r&&a[i]<a[l]) i++;

            j--;

            while (j>l&&a[j]>a[l]) j--;

            if (i<j) swap(a,i,j);

        }

        swap(a,l,j);

        if (j == k){

            return;

        }else if (j>k){

            quickSelect(a,l,j-1,k);

        }else{

            quickSelect(a,j+1,r,k);

        }

    }

    public void swap(int[] a,int x,int y){

        int tmp = a[x];a[x] = a[y];a[y] = tmp;

    }

}