排序

ccbb0530 · 2019-11-08 18:52:38 · 题解

// luogu.1177 今天我来给大家介绍luogu.1177的其他用法。\ 首先，sort的基本用法------递增法,下面是程序。

#include <bits/stdc++.h>

using namespace std;

int a[100005];

int main()
{
    int n;
    cin>>n;

    for (int i=1;i<=n;++i)
        cin>>a[i];

    sort(a+1,a+n+1);

    for (int i=1;i<=n;++i)
        cout<<a[i]<<" "; 
}

输入： 5 1 7 2 -1 6 输出： -1 1 2 6 7

很显然，这个排序不咋地（只能解决简单问题）。

第二种，下降法，下面是程序。

#include <bits/stdc++.h>

using namespace std;

int a[105];

int cmp(int a,int b){
    return a>b; 
}

int main()
{
    int n;
    cin>>n;

    for (int i=1;i<=n;++i)
        cin>>a[i];

    sort(a+1,a+n+1,cmp);

    for (int i=1;i<=n;++i)
        cout<<a[i]<<" "; 
}

输入： 5 1 7 2 -1 6 输出： 7 6 2 1 -1

以上就是基本的sort快排用法当然这不是最快的（最差O（n^2))。

优先级队列是个有用的东西，在这题中也适用。

#include <bits/stdc++.h>

using namespace std;

priority_queue<int,vector<int>,greater<int> >q;
int n,x;

int main()
{
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>x;
        q.push(x);
    }

    while(!q.empty()){
        cout<<q.top()<<' ';
        q.pop();
    }
    return 0;
}

桶排不是很常见，但是他的时间复杂度为O(n logn)

#include <bits/stdc++.h>

using namespace std;

int a[100005],i,temp;

void heap(int nn,int ii){
    int x,i,j;
    i=ii;          
    x=a[ii];    
    j=2*ii;    
    while (j<=nn){    
        if (j<nn && a[j]<a[j+1])   
            j++;
        if (x<a[j]){ 
            a[i]=a[j];  
            i=j;   
            j=2*i;   
        } 
        else 
            j=nn+1;  
    }  
    a[i] = x; 
}

int main()
{
    int n;
    cin>>n;

    for (i=1;i<=n;++i)
       cin>>a[i];

    for (i=n/2;i>=1;i--) 
        heap(n,i);

    for (i=n;i>=2;i--){
        swap(a[1],a[i]);
        heap(i-1,1);
    }
    for (i=1;i<=n;i++) cout<<a[i]<<" ";
}