P1177 【模板】排序题解

_Runtime_Error_ · 2024-08-08 09:59:31 · 题解

楼上大佬写的都是什么归并，希尔，基数，计数，快速，冒泡，选择，插入，可是我太蒟蒻了，不会这些排序方法，所以就来放一种新的方法

本人@AAAuc03 STL学者前来传授STL写法

采用自动排序但不去重的容器：multiset（不去重集合）、priority_queue（优先权队列）

头文件：

#include <set>

定义：

multiset<node> name;

插入：

name.insert(x)//在适当位置插入x

删除：

name.erase(x)//删除所有x，本代码不用

其他：

name.size()
name.empty()
name.begin()
name.end()

时间复杂度：O（logn）

遍历：

for(multiset<int>::iterator it=name.begin();it!=name.end();it++)
{
    cout<<*it<<" ";
}

实现方法：二叉排序树

      （10）

      /    \

    (5)     (20)

    / \     /  \

  (1) (10) (10) (30)

从图中可以看到,左边的子节点永远小于父节点，右边的子节点永远大于父节点，插入一个数就将这个数插入到排序树相应的位置。将这棵树中序遍历就得到最终的排序结果。~~代码本蒟蒻还不会写~~

setACcode

#include <bits/stdc++.h>//万能头，不需要其他头文件
#define set multiset<int>::iterator//太麻烦了
using namespace std;
multiset<int> s;//定义multiset
int main()
{
    int n,x;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        s.insert(x);//插入x到指定位置
    }
    for(set i=s.begin();i!=s.end();i++)
    {
        cout<<*i<<" ";//遍历输出
    }
    return 0;
}

set方法AC记录

头文件：

#include <queue>

定义：

priority_queue<node> q;//从大到小
priority_queue<node,vector<node>,greater<node> >q;//从小到大，本题解法

插入：

q.push(x);//将x插入到适当位置

删除：

q.pop();//删除第一个元素

其他：

q.size()
q.empty()
q.top()//首个元素

实现方法：二叉堆

二叉堆是基于二叉树实现，在二叉树里加上一定条件形成。

二叉堆分为两种：大根堆和小根堆

大根堆：任意一个父节点的值都大于等于其子节点的值

小根堆：任意一个父节点的值都小于等于其子节点的值

~~同样，代码不放（因为不会）~~

遍历可直接循环

代码时间再次到！

#include <bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> > s;//定义
int main()
{
    int n,x;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        s.push(x);//插入x到适当位置
    }
    for(int i=1;i<=n;i++)
    {
        cout<<s.top()<<" ";//输出第一个元素并将其弹出
        s.pop();
    }
    return 0;
}

queue方法AC记录

P1177 【模板】排序 题解

P1177 【模板】排序题解