题解 | #最小的K个数#

不让我用Arrays.sort我就用快排

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if(input.length>1){
            int left = 0;
            int right = input.length-1;
            QuickSort(input,left,right);
        }
//         Arrays.sort(input);
        ArrayList<Integer> ans = new ArrayList<Integer>();
        for(int i = 0; i < k; i++){
            ans.add(input[i]);
        }
        return ans;
    }

    public void QuickSort(int[] arr,int left,int right){
        if(left>right){
            return;
        }
        int base = arr[left];
        int i = left;
        int j = right;
        while(i<j){
            while(i<j && arr[j]>=base){
                j--;
            }
            while(i<j && arr[i]<=base){
                i++;
            }
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        arr[left] = arr[i];
        arr[i] = base;
        QuickSort(arr,left,i-1);
        QuickSort(arr,i+1,right);
    }
}