简单桶排序 -- B2096 直方图

· · 题解

题意简述

给定一个非负整数列 \{a_n\}，记 \text{Fmax}=\max\{a_n\}，并定义集合：

A=\{x\ |\ x\in\mathbb{N},0\le x\le \text{Fmax}\}

求集合 A 中的每一个元素在数列 \{a_n\} 中的出现次数。

解法

桶排序裸题。

桶排序的大概意思就是对于数集的值域 I 内的每一种取值都开一个计数器，称作桶，然后每读入一个数就把对应的计数器加一，即可完成排序。桶排序的原理类似平常的画正字。

在这道题中，我们不仅要对数列进行桶排序，还要在排序的过程中在线处理数列中的最大值，来确定 \text{Fmax} 的值。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=114514;
int bucket[maxn],n,tmp,Fmax;
//输入量比较大，使用快读快写
int read() {
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    int x=0;
    while(ch>='0'&&ch<='9') x=(x*10)+(ch^48),ch=getchar();
    return x;
}
void wr(int x) {
    if(x>9) wr(x/10);
    putchar(x%10+'0');
}
void write(int x, char ch='\n') {
    wr(x);
    putchar(ch);
}
int main(void) {
    n=read();
    while(n--) tmp=read(),++bucket[tmp],Fmax=(tmp>Fmax)?tmp:Fmax; //更新计数器和 Fmax
    for(int i=0;i<=Fmax;++i) write(bucket[i]);
    return 0;
}

扩展

桶排序的其它应用

桶排序还有另一个重要应用——去重。我们发现，在桶排序的过程中，序列中出现过的数，计数器的值不为 0，否则为 0。这可以帮助我们完成去重。详见 P1059 [NOIP2006 普及组] 明明的随机数。

另一道桶排练习题是 [CSP-J2020] 直播获奖，本题需要强制在线桶排，复杂度 n^2\log n 的 sort 无法通过。当然，这道题也可以用对顶堆，平衡树等多种方法通过。

桶排序的优劣分析

桶排序是目前可以用计算机实现的时间复杂度最优的排序算法，复杂度是严格 O(n) 的，而且常数极小（数组索引 1 次，自增 1 次）。

然而，优秀的时间复杂度使用空间复杂度换取的。桶排序的空间复杂度是 O(\max a-\min a)，如果数据开到 [1,10^8]，桶排序就会彻底挂掉（因为会有非常大的空间浪费）。