题解 P1177 【【模板】快速排序】

这篇题解来源于一个大胆的想法

桶排序有着极高的运行速度,却是一种用空间换时间的算法,具有很大的局限性,无法用来排太大的数据

于是,用map代替数组,以时间换空间,达到扩大实用性的目的

C++STL中map<int,int>可以当作数组来用，类比桶排序，但是因为map是动态申请储存空间，相当于自动离散化，解决以前的空间浪费

用迭代器遍历map节省时间，跳过空白部分

接下来上代码压压惊，（操作什么的，还是很简单）

#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.广告： 蒟蒻的博客