题解 | #输入n个整数，输出其中最小的k个#

题解思路：输出最小的k个数，我首先想到的是先排序再遍历输出。但排序用哪种方式好呢？感觉冒泡、插入、选择都可以，只需要排出前k个即可，快排和归并感觉不是很有必要，因为这样会将所有数据进行排序，有些多此一举。当然对于Top k 类型的算法，堆排序肯定是最佳的选择。Java中PriorityQueue是通过完全二叉树实现的小顶堆，使用起来很方便，省去了自己构建堆的麻烦。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner scanner = new Scanner(br);
        int num = scanner.nextInt();
        int k = scanner.nextInt();
        int[] nums = new int[num];
        for (int i = 0; i < num; i++) {
            nums[i] = scanner.nextInt();
        }
        String result = getSmallestNumberOfK_2(nums,k);
        System.out.println(result);
    }
    // 投机取巧的解法
    private static String getSmallestNumberOfK_3(int[] nums, int k) {
        if (k <= 0 || nums == null || nums.length == 0) return null;
        StringBuilder builder = new StringBuilder();
        Arrays.sort(nums);
        for (int i = 0; i < k; i++) {
            builder.append(nums[i]).append(" ");
        }
        return builder.toString().trim();
    }
    // 使用堆排序解决
    private static String getSmallestNumberOfK_2(int[] nums, int k) {
        if (k <= 0 || nums == null || nums.length == 0) return null;
        StringBuilder builder = new StringBuilder();
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int i = 0; i < nums.length; i++) {
            heap.add(nums[i]);
        }
        for (int i = 0; i < k; i++) {
            builder.append(heap.poll()).append(" ");
        }
        return builder.toString().trim();
    }
    // 使用选择排序解决
    private static String getSmallestNumberOfK_1(int[] nums,int k) {
        if (k <= 0 || nums == null || nums.length == 0) return null;
        StringBuilder builder = new StringBuilder();
        selectort(nums,k);
        for (int i = 0; i < k; i++) {
            builder.append(nums[i]).append(" ");
        }
        return builder.toString().trim();

    }

    private static void selectort(int[] nums,int k) {
        int min;
        for (int i = 0; i < nums.length-1; i++) {
            min = i;
            for (int j = i+1; j < nums.length; j++) {
                if (nums[j] < nums[min]){
                    min = j;
                }
                if (i == k) break;
            }
            if (min != i)
                swap(nums,i,min);
        }
    }
    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

}