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

此题解法：快排、优先队列、treemap、最大数据范围…

第四十题，最简单的就是使用冒泡排序，然后直接返回k长度的数组就可以，这个不多说。

主要记录一下今天在题解中学到的快速排序方法，首先来一个自己后来写的快排示例替代冒泡。

public void quickSearch(int[] arr, int lo, int hi){
        if (lo > hi) {
            return;
        }
        
        int start = lo;
        int end = hi + 1;
        int v = arr[lo];
        while (true) {
            while (--end >= lo && arr[end] > v);
            while (++start <= hi && arr[start] < v);
            if(start >= end){
                break;
            }
            int t = arr[end];
            arr[end] = arr[start];
            arr[start] = t;
        }

        arr[lo] = arr[end];
        arr[end] = v;
        
        quickSearch(arr, lo, end - 1);
        quickSearch(arr, end + 1, hi);
    }

和冒泡排序相比，冒泡时间复杂度O(n^2^)，快排时间复杂度为O(nlog2n)，如何用快排实现本题呢？上代码：

class Solution4 {

    /**
     * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
     */
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k == 0 ||  arr.length < k){
            return new int[0];
        }
        return sort(arr, 0, arr.length - 1, k - 1);
    }

    public int[] sort(int[] arr, int lo, int hi, int k){
        // 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的
        int j = quickSort(arr, lo, hi);
        if(j == k) {
            return Arrays.copyOf(arr, j + 1);
        }

        // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
        return j > k ? sort(arr, lo, j - 1, k) : sort(arr, j + 1, hi, k);
    }

    public int quickSort(int[] arr, int lo, int hi){
        int i = lo;
        int j = hi + 1;
        // 假设临界的值
        int v = arr[lo];
        while(true) {
            while(--j >= lo && arr[j] > v);
            while(++i <= hi && arr[i] < v);
            if(i >= j) {
                break;
            }
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }

        // 将临界值和j所在位置进行替换
        arr[lo] = arr[j];
        arr[j] = v;
        return j;
    }

提交后效率占比还是非常可观的：

至此，快排完美完成，解释都在代码内，日后自己不懂再来光顾。