JZ29-TOPK_Small

//插入排序思想
class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (input == null || input.length == 0 || k > input.length) {
            return list;
        }
        for (int i = 0; i < k; i++) {
            for (int j = input.length - 1; j > 0; j--) {
                if (input[j] < input[j - 1]) {
                    int temp = input[j];
                    input[j] = input[j - 1];
                    input[j - 1] = temp;
                }
            }
            list.add(input[i]);
        }
        return list;
    }
}

//堆排序思想
class Solution2 {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (input == null || input.length == 0 || k > input.length || k == 0) {
            return list;
        }
//        Queue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return o2.compareTo(o1);  //重写这里的方法  o1.compareTo(o2) 从小到大  反过来 从大到小
//            }
//        });

        Queue<Integer> maxHeap = new PriorityQueue<>(k, (o1, o2) -> o2 - o1);

        for (int i = 0; i < input.length; i++) {
            if (maxHeap.size() != k) {  //先把堆装满
                maxHeap.offer(input[i]);
            } else if (input[i] < maxHeap.peek()) {
                maxHeap.poll();
                maxHeap.offer(input[i]);
            }
        }
        for (Integer val : maxHeap) {
            list.add(val);
        }
        return list;
    }
}
//快排思想
class Solution3 {
    public static int GetLeastNumbers_Solution(int[] arr, int k) {
        if (arr == null || arr.length < k) {
            return -1;
        }
        int partition = partition(arr, 0, arr.length - 1);

        while (partition + 1 != k) {  //要一直循环查找，类似于递归的终止条件，while结束了，才能执行下面的return，跳出递归
            if (partition + 1 < k) {  //如果是if的话，只执行一次就执行return跳出递归了
                partition = partition(arr, partition + 1, arr.length - 1);
            } else { //partition + 1 > k
                partition = partition(arr, 0, partition - 1);
            }
        }
        return arr[partition];  //partition + 1 = k 即第k小的数
    }

    //此函数将分区点放到正确的位置上
    private static int partition(int[] a, int p, int r) {

        int pivot = a[r];
        int i = p;

        for (int j = p; j < r; j++) {
            if (a[j] <= pivot) {
                swap(a, i, j);  //工具函数
                i++;
            }
        }
        swap(a, i, r);
        return i;
    }

    private static void swap(int[] a, int i, int j) {
        if (i == j) {
            return;
        }
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}