题目描述

输入一个长度为n的整数数列，从小到大输出前m小的数。

输入格式
第一行包含整数n和m。

第二行包含n个整数，表示整数数列。

输出格式
共一行，包含m个整数，表示整数数列中前m小的数。

样例

输入样例：
5 3
4 5 1 3 2
输出样例：
1 2 3

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C代码

#include<stdio.h>
const int N=100010;    //必须加const
int tree[N];
void swap(int a, int b)
{
    int c;
    c = tree[a];
    tree[a] = tree[b];
    tree[b] = c;
}
void heapify(int n,int i)
{
    int l1=2*i+1;
    int l2=2*i+2;
    int max=i;
    if(l1<n&&tree[max]<tree[l1]) max=l1;    //一定注意判断边界
    if(l2<n&&tree[max]<tree[l2]) max=l2;
    if(max!=i) 
    {
        swap(i,max);
        heapify(n,max);                     //不要到外面去递归
    }
}
void creat_heap(int n)
{

    for(int i=(n-2)/2;i>=0;i--)           //这是建堆最好的点。当然你可以最多从最后一个非叶结点开始建
    {
        heapify(n,i);                     //不过显然不必要
    }
}
void heap_sort(int n)
{
    creat_heap(n);
    for(int i=n-1;i>=0;i--)
    {
        swap(i,0);
        heapify(i,0);                    //i--就相当于n--,“砍断操作”
    }
}
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++) scanf("%d",&tree[i]);
    heap_sort(n);
    for(int i=0;i<m;i++)
    {
        printf("%d ",tree[i]);
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla