桶排序

基础知识 / bucket-sort

本地源文件：docs/basic__bucket-sort.md

桶排序

本页面将简要介绍桶排序．

定义

桶排序（英文：Bucket sort）是排序算法的一种，适用于待排序数据值域较大但分布比较均匀的情况．

过程

桶排序按下列步骤进行：

  1. 设置一个定量的数组当作空桶；
  2. 遍历序列，并将元素一个个放到对应的桶中；
  3. 对每个不是空的桶进行排序；
  4. 从不是空的桶里把元素再放回原来的序列中．

性质

稳定性

如果使用稳定的内层排序，并且将元素插入桶中时不改变元素间的相对顺序，那么桶排序就是一种稳定的排序算法．

由于每块元素不多，一般使用插入排序．此时桶排序是一种稳定的排序算法．

时间复杂度

桶排序的平均时间复杂度为 𝑂(𝑛 +𝑛2/𝑘 +𝑘)O(n+n2/k+k)（将值域平均分成 𝑛n 块 + 排序 + 重新合并元素），当 𝑘 ≈𝑛k≈n 时为 𝑂(𝑛)O(n)．1

桶排序的最坏时间复杂度为 𝑂(𝑛2)O(n2)．

实现

C++Python

---|---

---|---

参考资料与注释

  1. （英文）Bucket sort - Wikipedia ↩
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Enter-tainer, Marcythm, NachtgeistW, iamtwz, ouuan, Tiphereth-A, Menci, partychicken, shawlleyw, Xeonacid 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用