题解 P1177 【【模板】快速排序】
安昙
2018-08-27 20:35:31
## ~~这篇题解来源于一个大胆的想法~~
### 桶排序有着极高的运行速度,却是一种用空间换时间的算法,具有很大的局限性,无法用来排太大的数据
### 于是,用map代替数组,以时间换空间,达到扩大实用性的目的
------------
C++STL中map<int,int>可以当作数组来用,类比桶排序,但是因为map是动态申请储存空间,相当于自动离散化,解决以前的空间浪费
------------
用迭代器遍历map节省时间,跳过空白部分
------------
接下来上代码压压惊,(操作什么的,还是很简单)
```cpp
#include<bits/stdc++.h>
#define getc getchar()
using namespace std;
map<int,int> k;//定义k桶
int n;
map<int,int>::iterator it;//定义迭代器it
int s[60000];
int read()//快读 ,不解释了
{
int x=0;
char c;
for(c=getc;c>'9'||c<'0';c=getc);
for(;c<='9'&&c>='0';c=getc)x=x*10+c-'0';
return x;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
int tis;
tis=read();
k[tis]++;//装入桶内
}
for(it=k.begin();it!=k.end();it++)//迭代器遍历,不了解请百度
{
for(int i=1;i<=it->second;i++)//map内元素是pair类型的,例如a[123]=666; 则first指123,second指666,以此类推
{//迭代器指向该元素的出现次数second
int sum=it->first;//迭代器指向该元素first
printf("%d ",sum);//输出
}
}
}
```
## 实测:速度为桶排序的25%
## o2优化后快3倍
------------
### PS.广告: [蒟蒻的博客](https://www.luogu.org/blog/naruto-lfk/)