题解 | #最小的K个数#

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> resList = new ArrayList<>();
        if (input == null||input.length==0) {
            return resList;
        }

        quickSortList(input, 0, input.length - 1);

        for (int i = 0; i < k; i++) {
            resList.add(input[i]);
        }

        return resList;
    }


    public void quickSortList(int[] input, int low, int high) {
        int pow = quickSort(input, low, high);
        if(pow>low){
           quickSortList(input, low, pow-1);
        }
        if(pow<high){
            quickSortList(input, low + 1, high);
        }
    }

    public int quickSort(int[] input, int low, int high) {
        int piot = input[low];
        while (low < high) {
            while (low < high && input[high] >= piot) {
                --high;
            }

            input[low] = input[high];

            while (low < high && input[low] <= piot) {
                ++low;
            }
            input[high] = input[low];
        }
        input[low] = piot;
        return low;
    }
}