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

• 示例 1：
  输入：arr = [3,2,1], k = 2
  输出：[1,2] 或者 [2,1]

• 示例 2：
  输入：arr = [0,1,2,1], k = 1
  输出：[0]

• 限制：
  0 <= k <= arr.length <= 10000
  0 <= arr[i] <= 10000

1 解法

直接选择排序，再获取对应前k个值：

public int[] getLeastNumbers(int[] arr, int k) {
      for(int i=0;i<arr.length;i++){
            for(int j=i;j<arr.length;j++){
                if(arr[i]>arr[j]){
                    arr[i]=arr[i]^arr[j];
                    arr[j]=arr[i]^arr[j];
                    arr[i]=arr[i]^arr[j];
                }
            }
        }
        return Arrays.copyOf(arr,k);
    }

简单且暴力，就是效率低，重新回顾下几种排序算法，及对应排序的代码。

2 排序算法

排序算法时间空间复杂度

这里只重点说明快速排序，其他的太简单的没必要说明。

3 快速排序

思路分析：快速排序采用双向查找的策略，每一趟选择当前所有子序列中的一个关键字作为枢纽轴，将子序列中比枢纽轴小的前移，比枢纽轴大的后移，当本趟所有子序列都被枢轴按上述规则划分完毕后将会得到新的一组更短的子序列，他们将成为下趟划分的初始序列集。
时间复杂度：最好情况（待排序列接近无序）时间复杂度为O(nlog2n)，最坏情况（待排序列接近有序）时间复杂度为O(n2)，平均时间复杂度为O(nlog2n)。
代码如下：

 /***
     * 快速排序主入口
     */
    public static void quickSort(int[] array,int begin,int end){
        if(begin>=end){
            return;
        }
        int i = swapArray(array,begin,end);
        quickSort(array,begin,i-1);
        quickSort(array,i+1,end);
    }

    /***
     * 元素交换
     */
    public static int swapArray(int[] array,int begin,int end){
        int i=begin;
        int j=end;
        int k = array[i];
        while(i<j){
            // 从右往左遍历，遇到小于k值的放入array[i]中
            while(i<j && array[j]>=k ){
                j--;
            }
            if(i<j){
                array[i] = array[j];
                i++;
            }

            // 从左往右遍历，遇到大于k的放array[j]中
            while(i<j && array[i]<k){
                i++;
            }
            if(i<j){
                array[j] = array[i];
                j--;
            }
        }
        array[i]=k;
        return i;
    }