#tp001. 桶排序

桶排序

桶排序

题目描述

​ 给定 n个整数xix_i,每个整数的取值范围为 [1,1000]。请使用桶排序(计数排序) 的思想,将这些整数按从小到大的顺序输出(包含重复元素,即每个出现几次就输出几次)。

算法概念

​ 桶排序(Bucket Sort) 是一种通过“分桶”映射来排序的算法。当待排序数据为整数且值域范围较小时,可以退化为计数排序(Counting Sort):每个桶只对应一个数值,桶内存储该数值出现的次数,最后按顺序遍历桶并输出。

算法原理与步骤

  1. 确定值域:本题数值范围为 [1,1000],因此桶的数量固定为 1000。
  2. 初始化桶:创建一个大小为 1001(或 1000)的整型数组 bucket,所有元素初始化为 0。下标 i代表数值 i(若从 1 开始)。
  3. 统计频次:遍历输入的 n个整数,每读到一个数 x,执行 bucket[x]++。
  4. 输出结果:从小到大遍历下标 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),但本题已固定范围,可直接使用常量。