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

排序算法第3篇，简单选择排序和堆排序

#include <algorithm>
#include <vector>

using namespace std;

void maxsift(vector<int> &v,int start,int end){
    if(start==end) return;
    int temp = v[start];
    
    if(2*start+1==end){
        if(v[start]<v[end]){
            v[start] = v[end];
            start = end;
        }
    }//这里处理第0号和第1号的情况
    
    for(int i = start*2+1;i<end;i=i*2+1){//这里没有=end
        if(v[start*2+1]<v[start*2+2])++i;
        if(temp>v[i]) break;
        v[start] = v[i];
        start = i;
        
    }
    
    v[start] = temp;
}



vector<int> & mysort(vector<int> & v){
    
    /*int n = v.size();
    for(int i = 1;i<n;i++){
        int min = INT16_MAX;
        int mincood = 0;
        for(int j = i-1; j<n;j++){
            if(v[j]<min){
                min = v[j];
                mincood = j;
            }
        }
        swap(v[mincood], v[i-1]);
    }简单选择排序*/
    
    int n = v.size();
    for(int i =(n-2)/2;i>=0;i--){
        maxsift(v,i,n-1);
    }
    for(int i=n-1;i>0;i--){
        swap(v[0], v[i]);
        maxsift(v,0,i-1);
    }
    
    
    
    
    return v;
}


int main() {
    int n,k;
    while(cin>>n>>k){
        vector<int> v;
        int temp=0;
        for(int i = 0;i<n;i++){
            cin>>temp;
            v.push_back(temp);
            
        }
        
        v=mysort(v);
        for(int j = 0;j<k;j++){
            cout<<v[j]<<' ';
            
        }
        
    }
}