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

排序算法总结1

#include <algorithm>
#include <vector>

using namespace std;

vector<int> & mysort(vector<int> & v){
    /*int temp;
    for(int i = 1;i<v.size();i++){
        if(v[i]<v[i-1]){
            temp = v[i];
        
       
        int j;
        for(j=i;v[j-1]>temp&&j>0;j--){
            
            v[j] = v[j-1];
        }
        v[j]=temp;
        }
        
    }直接插入排序*/
    
    /*for(int i =1;i<v.size();i++){
        int temp = v[i];
        int low = 0,high = i-1;
        while(low<=high){
            int m = (low+high)/2;
            if(v[i]>v[m])low=m+1;
            else if(v[i]<v[m]) high = m-1;
            else if(v[i]==v[m]){
                high = m;
                break;
            }
        }//while
            for(int j = i;j>high+1;j--){
                v[j]=v[j-1];
            }
            v[high+1] = temp;
        
    }//for折半插入算法*/
    /*int n =v.size();
    vector<int> vtemp(n,0);
    vtemp[0]=v[0];
    int first=0,last = 0;
    for(int i = 1;i<n;i++){
        
        if(v[i]<vtemp[first]){
            first = (first-1+n)%n;
            vtemp[first] = v[i];
        }
        else if(v[i]>vtemp[last]){
            last = (last+1+n)%n;
            vtemp[last] = v[i];
        }
        else{
            int k = last;
            last = (k+1+n)%n;
            while(vtemp[k]>v[i]){
                vtemp[(k+1+n)%n] = vtemp[k];
                k=(k-1+n)%n;
            }
            k=(k+1+n)%n;
            vtemp[k]=v[i];
        }
        
        
    }//for
    for(int i = 0;i<n;i++){
        v[i] = vtemp[first];
        first = (first+1+n)%n;
    }2路插入*/
    
    
    /*int n = v.size();
    class Node{
        public:
        int key;
        int next;
    };
   Node r[n+1];
    r[0].next = 1;
    r[1].next = 0;
    r[0].key = INT16_MAX;
    for(int i =1;i<n+1;i++){
        r[i].key=v[i-1];
    }
    for(int i = 2;i<n+1;i++){
       int temp = r[0].next;
        int prev = 0;
        while(r[i].key>r[temp].key){
            prev = temp;
            temp=r[temp].next;
        }
        r[prev].next = i;
        r[i].next = temp;
    }
    int p = r[0].next;
    for(int i =1;i<n+1;i++){
        while(p<i)p=r[p].next;
        int temp = r[p].next;
        swap(r[p],r[i]);
        r[i].next = p;
        p = temp;
        
    }
    for(int j = 0;j<n;j++){
        v[j] = r[j+1].key;
    }表插入法的排序*/
    
  
    
    
    
    
    
    
    
    
    
    
    sort(v.begin(),v.end());//STL自带的算法
    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]<<' ';
            
        }
        
    }
}