快速选择，适用于寻找无序数组中第k大（小）或者前k大（小）这种情况，即TopK问题，是快速排序的一种变化。

class Solution {

  public static int[] getLeastNumbers(int[] arr, int k) {
      return quickSelect(arr,k,0,arr.length-1);
  }

  private static int[] quickSelect(int[] arr,int k,int l, int r){
      if (arr.length <= k){
          return arr;
      }
      int index = quickSort(arr,l,r);
      if (index == k){
          return Arrays.copyOf(arr,index);
      }else if (index < k){
          return quickSelect(arr,k,index+1,r);
      }else {
          return quickSelect(arr,k,l,index-1);
      }
  }

  private static int quickSort(int[] arr, int l, int r) {
      int mid = l ,i = l, j = r;
      while (i < j){
          while (i<j && arr[j] >= arr[mid]){
              --j;
          }
          if(i<j && arr[j] < arr[mid]){
              swap(arr,j,mid);
              mid = j;
          }
        //  p(arr);
          while (i<j && arr[i] <= arr[mid]){
              ++i;
          }
          if(i<j && arr[i] > arr[mid]){
              swap(arr,i,mid);
              mid = i;
          }
        //  p(arr);
      }
      swap(arr,i,mid);
      return mid;
  }


  private static void swap(int[] arr, int i, int j) {
      int tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
  }

  public static void p(int[] arr){
      for (int n:arr){
          System.out.print(n+" ");
      }
      System.out.println();
  }
}