题解 | #最小的K个数#

快排

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param input int整型一维数组
     * @param k int整型
     * @return int整型ArrayList
     */
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        if (k == 0 || input.length == 0) return new ArrayList<>();
        ArrayList<Integer> res = new ArrayList<>();
        quickSort(input, 0, input.length - 1);
        for (int i = 0; i < k; i++) {
            res.add(input[i]);
        }
        return res;
    }

    public  void quickSort(int[] arr, int i, int j) {
        int start = i, end = j;
        //递归的出口
        if (start >= end) return;
        //第一遍找出第一个元素在数组中的位置
        int pivot = arr[start];
        //找出 end 向前遍历比 pivot 小的数字，找出 start 向前遍历得到的数字，交换，然后重复这个过程
        while (start != end) {
            while (true) {
                if (end <= start || arr[end] < pivot) {
                    break;
                }
                end--;
            }
            while (true) {
                if (end <= start || arr[start] > pivot) {
                    break;
                }
                start++;
            }
            //交换元素
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }

        //结束循环之后，start 和 end 指向的位置即为 pivot 该存放的位置
        //将 pivot 归位
        int tmp = arr[i];
        arr[i] = arr[start];
        arr[start] = tmp;

        quickSort(arr, i, start - 1);
        quickSort(arr, start + 1, j);
    }
}