堆：剑指 Offer 40. 最小的k个数-526互联

题目描述：

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

限制：

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

题解：
本题使用排序算法解决最直观，对数组 arr 执行排序，再返回前 k 个元素即可。

快速排序原理：
快速排序算法有两个核心点，分别为 “哨兵划分” 和 “递归” 。

哨兵划分操作：以数组某个元素（一般选取首元素）为基准数，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。

递归：对左子数组和右子数组递归执行哨兵划分，直至子数组长度为 1 时终止递归，即可完成对整个数组的排序。

如下图所示，为示例数组 [2,4,1,0,3,5] 的快速排序流程。观察发现，快速排序和二分法的原理类似，都是以 \loglog 时间复杂度实现搜索区间缩小。

复杂度分析：
　　时间复杂度 O(NlogN) ：库函数、快排等排序算法的平均时间复杂度为 O(NlogN) 。
　　空间复杂度 O(N) ：快速排序的递归深度最好（平均）为 O(logN) ，最差情况（即输入数组完全倒序）为 O(N)。

class Solution{
    public int[] getLeastNumbers(int arr[],int k){
        quickSort(arr,0,arr.length-1);
        return Arrays.copyOf(arr,k);
    }
    public void quickSort(int arr[],int l,int r){
        // 子数组长度为 1 时终止递归
        if(l>=r) return;
        // 哨兵划分操作（以 arr[l] 作为基准数）
        int i=l,j=r;
        while(i<j){
            while (i<j&&arr[j]>=arr[l]) j--;
            while(i<j&&arr[i]<=arr[l]) i++;
            swap(arr,i,j);
        }
        swap(arr,i,l);
        // 递归左（右）子数组执行哨兵划分
        quickSort(arr,l,i-1);
        quickSort(arr,i+1,r);
    }
    public void swap(int arr[],int l,int r){
        int t = arr[l];
        arr[l] = arr[r];
        arr[r] = t;
    }
}

注：

Arrays.copyOf(array, to_index);
Arrays.fill(array, from_index, to_index);

第一个方法其实就是返回一个数组，而这个数组就等于数组array的前to_index个数，也就是array[0] ~ array[to_index - 1]。

而第二种方法也只是加了一个初始的位置，即返回一个数组等于array[from_index] ~ array[to_index - 1]。

这里要注意一下，不管是上面哪种使用方法，都务必记住不包含array[to_index]这个数。