题目描述

blablabla

样例

blablabla

算法1

Java 代码

import java.util.*;
import java.io.*;

public class Main{

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        heapSort(arr);
        for(int i = 0; i < m; i++){
            System.out.print(arr[i] + " ");
        }

    }

    /**
     * 堆排序
     */
    private static void heapSort(int[] arr) { 
        // 将待排序的序列构建成一个大顶堆 O(n)
        for (int i = arr.length / 2; i >= 0; i--){ 
            //从第一个非叶子结点从下至上，从右至左调整结构
            heapAdjust(arr, i, arr.length - 1); 
        }

        // 逐步将每个最小值的根节点与末尾元素交换，并且再调整二叉树，使其成为大顶堆
        for (int i = arr.length - 1; i > 0; i--) { 
            swap(arr, 0, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
            heapAdjust(arr, 0, i); // 交换之后，需要重新检查堆是否符合大顶堆，不符合则要调整
        }
    }

    /**
     * 构建堆的过程
     * @param arr 需要排序的数组
     * @param k 需要构建堆的根节点的序号
     * @param n 数组的长度
     */
    private static void heapAdjust(int[] arr, int parent, int length) {
        int temp = arr[parent];//先取出当前元素i
        int lc = 2*parent + 1;
        while(lc < length){
            // 如果有右孩子结点，并且右孩子结点的值 小雨于左孩子结点，则选取右孩子结点
            if(lc < length -1 && arr[lc] < arr[lc+1]){
                lc++;
            }
            // 如果父结点的值已经小于孩子结点的值，则直接结束
            if (temp >= arr[lc]){
                break;
            }else{
                // 把孩子结点的值赋给父结点
                arr[parent] = arr[lc];
                parent = lc;
                lc = 2*lc + 1;
            }
        }
        arr[parent] = temp;
    }

    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }


}