基础算法学习以及$STL$的使用

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了基础算法学习以及$STL$的使用，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2474字，纯文字阅读大概需要4分钟。

内容图文

1.优先队列

(1)大根堆（小顶堆）

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

(2)小根堆（大顶堆）

priority_queue<int, vector<int>, less<int> >q;
//或者
priority_queue<int>q;

用法

q.push(x);//入队列

q.pop();//堆顶值

q.back();//队尾值

q.pop();//出队列

q.empty();//返回q是否为空，空则返回1，否则返回0

q.size();//返回q里元素个数

2.排序

(1)快排(STL万岁！\(QwQ\))

sort(a+1,a+n+1);//a数组1~n从小到大排序

(2)结构体排序

//定义
struct node{
int x,y;
};
node a[maxn];
//先从小到大按x值排序，再从大到小按y值排序
bool cmp(node s1,node s2){
if(s1.x!=s2.x)return s1.x<s2.x;
return s1.y>s2.y;
}
//主函数内
sort(a+1,a+n+1,cmp);

(3)结构体内重载运算符

struct node
{
    int x,y;
    bool operator < (const node & a) const
    {
        return x<a.x;
    }
};

(4)归并排序

#include<cstdio>
#include<cmath>
#include<set>
#include<stack>
#include<queue>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define _for(i,a,b) for(int i=a;i<=b;i++)
#define maxn 500005
using namespace std;
typedef long long ll;
int t[100005],ans=0;
int n,a[100005];

int read(){
    int f=1,ans=0;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        ans=ans*10+c-'0';
        c=getchar();
    }
    return f*ans;
}

void gb(int a[],int l,int r){ 
    if(l==r)
    return;
    int mid=(l+r)/2;
    gb(a,l,mid); 
    gb(a,mid+1,r);
    int i=l,j=mid+1,p=l;
    while(i<=mid&&j<=r){
        if(a[i]>a[j]){
            t[p++]=a[j++];
            ans+=mid-i+1;        }
        else
        t[p++]=a[i++];
    }
    while(i<=mid)
    t[p++]=a[i++];
    while(j<=r)
    t[p++]=a[j++];
    for(i=l;i<=r;i++)
    a[i]=t[i];
}
int main(){

    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    gb(a,1,n);
    cout<<ans<<endl;
    return 0;
}

(5)手写快排

int a[101];

void hand_write_quick_sort(int l,int r)
{
    if(l>=r) return;
    else
    {
        int i=l;
        int j=r;
        int top=a[i];
        //a[i]即为我们选择的“点”，用于分割
       //（我们用的是这个点的值，而不是位置。）
        while(i<j)
        {
         while(top<=a[j] && (i<j)) j--;
         //a[j]比top大，则换下一个进行比较
         a[i]=a[j];//"点"的位置变为a[j]
         while(a[i]<=top && (i<j)) i++;
         //a[i]比top小，则换下一个进行比较
         a[j]=a[i];//"点"的位置变为a[i]
         }        //小的往前去，大的往后退。
        a[i]=top;
        hand_write_quick_sort(l,i-1);
        hand_write_quick_sort(i+1,r);
    }
}

//l~r中第k大的数（分治）
LL get(int l, int r, int k)
{
    if (l == r) return a[k];
    int u = l + rand() % (r-l+1);
    LL v = a[u];
    swap(a[l], a[u]);

    int i = l, j = r;
    while (i < j)
    {
        while (i < j && a[j] >= v) j--;
        if (i < j) { a[i] = a[j], i++; }
        while (i < j && a[i] < v) i++;
        if (i < j) { a[j] = a[i], j--; }
    }
    a[i] = v;

    while (i < (l+r)/2 && a[i] == a[i+1]) i++;

    if (k < i) return get(l, i-1, k);
    else if (k > i) return get(i+1, r, k);
    else return v; 
}

内容总结

以上是互联网集市为您收集整理的基础算法学习以及$STL$的使用全部内容，希望文章能够帮你解决基础算法学习以及$STL$的使用所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---