#tp001. 桶排序
桶排序
桶排序
题目描述
给定 n个整数,每个整数的取值范围为 [1,1000]。请使用桶排序(计数排序) 的思想,将这些整数按从小到大的顺序输出(包含重复元素,即每个出现几次就输出几次)。
算法概念
桶排序(Bucket Sort) 是一种通过“分桶”映射来排序的算法。当待排序数据为整数且值域范围较小时,可以退化为计数排序(Counting Sort):每个桶只对应一个数值,桶内存储该数值出现的次数,最后按顺序遍历桶并输出。
算法原理与步骤
- 确定值域:本题数值范围为 [1,1000],因此桶的数量固定为 1000。
- 初始化桶:创建一个大小为 1001(或 1000)的整型数组 bucket,所有元素初始化为 0。下标 i代表数值 i(若从 1 开始)。
- 统计频次:遍历输入的 n个整数,每读到一个数 x,执行 bucket[x]++。
- 输出结果:从小到大遍历下标 i=1→1000,若 bucket[i] > 0,则连续输出 bucket[i] 次数字 i。
输入格式
第一行一个正整数 n,表示数字个数。
第二行 n 个整数,每个数在 [1,1000]之间。
输出格式
一行,输出排序后的 n个整数,相邻数字用空格隔开。
输入输出样例
5
3 1 2 1 3
1 1 2 3 3
数据规模与约定
1≤n≤1000
数值范围:1≤x≤1000
提示
代码提示:
const int MAX_VAL = 1000; // 数值最大值
int bucket[MAX_VAL + 1] = {0}; // 桶数组,下标代表数值
int n;
cin >> n;
// 1. 统计频次
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
// 将 x 映射到桶下标,并累加计数
// 提示:bucket[?]++
}
// 2. 输出有序序列(不去重)
for (int i = 1; i <= MAX_VAL; i++) {
// 如果 bucket[i] > 0,则连续输出 bucket[i] 次 i
}
运用提示:
桶排序的核心在于 “用空间换时间”,本题值域固定,桶大小确定,十分适合练习模板。
如果数值范围不是固定的,可以动态求出最大值和最小值,再分配桶(大小 = 最大值 - 最小值 + 1),但本题已固定范围,可直接使用常量。