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

排序算法第四篇,归并排序

#include <algorithm>
#include <vector>

using namespace std;

void merge(vector<int> &L,int left,int mid,int right){
    vector<int> R(L.size(),0);
    int i,j,k;
    for(i = left,j=mid+1,k=left;i<=mid&&j<=right;){
        if(L[i]<L[j])R[k++]=L[i++];
        else R[k++]=L[j++];
    }
    while(j<=right){
        R[k++]=L[j++];
    }
    while(i<=mid){
        R[k++]=L[i++];
    }
    for(int i = left;i<=right;i++){
        L[i]=R[i];
    }
    
}


vector<int> & mysort(vector<int> & v,vector<int> &v1,int low,int high){
    if(low==high)v1[low]=v[low];
    else{
        int m = (low+high)/2;
        mysort(v, v1, low, m);
        mysort(v, v1, m+1, high);
        merge(v1, low, m, high);
    }
    
    
    return v1;
}


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);
        }
        vector<int> v1(n,0);
        v1=mysort(v,v1,0,n-1);
        for(int j = 0;j<k;j++){
            cout<<v1[j]<<' ';
        }
        
    }
}