1. 引言为什么需要桶排序想象一下你有一堆大小不一的苹果需要按重量从小到大排好。最笨的方法是两两比较但有没有更快的办法呢桶排序Bucket Sort就是一种“分而治之”的排序思想先把苹果按重量范围分到几个桶里比如 0-50克、50-100克、100-150克然后在每个桶内分别排序最后按桶的顺序依次倒出就得到了有序序列。它特别适合处理数据分布均匀、范围已知的场景比如考试成绩排序、年龄统计等平均时间复杂度可以达到O(n)比常见的快速排序、归并排序还要快2. 核心思想分桶、排序、合并桶排序的核心步骤只有三步分桶Scatter确定桶的数量和范围把每个元素放入对应的桶中。桶内排序Sort对每个非空桶内的元素进行排序可以用任意排序算法如插入排序。合并Gather按桶的顺序从小到大依次取出所有元素得到最终有序序列。下面我们通过一个具体例子来直观理解。3. 图解桶排序一步一步看明白假设我们要对以下 8 个在 [0, 1) 区间内的小数进行排序[0.42, 0.32, 0.87, 0.12, 0.95, 0.63, 0.71, 0.29]步骤 1创建桶并分桶我们创建 10 个桶每个桶负责一个 0.1 的区间桶 0: [0.0, 0.1)桶 1: [0.1, 0.2)…桶 9: [0.9, 1.0)遍历数组把每个数放入对应的桶桶 0: [] 桶 1: [0.12] 桶 2: [0.29] 桶 3: [0.32, 0.42] 桶 4: [] 桶 5: [] 桶 6: [0.63] 桶 7: [0.71] 桶 8: [0.87] 桶 9: [0.95]步骤 2桶内排序对每个非空桶内的元素进行排序这里桶 3 有两个元素需要排序桶 1: [0.12] → 已有序桶 2: [0.29] → 已有序桶 3: [0.32, 0.42] → 排序后为 [0.32, 0.42]桶 6: [0.63] → 已有序桶 7: [0.71] → 已有序桶 8: [0.87] → 已有序桶 9: [0.95] → 已有序步骤 3合并桶按桶的顺序0 到 9依次取出所有元素[0.12, 0.29, 0.32, 0.42, 0.63, 0.71, 0.87, 0.95]排序完成4. 代码实现Python理解了原理代码就很简单了。下面是一个通用的桶排序实现假设输入是范围在 [0, 1) 的浮点数。defbucket_sort(arr): 桶排序针对 [0, 1) 区间的浮点数 :param arr: 待排序数组 :return: 排序后的数组 nlen(arr)ifn1:returnarr# 1. 创建 n 个空桶buckets[[]for_inrange(n)]# 2. 分桶将每个元素放入对应的桶中fornuminarr:bucket_indexint(num*n)# 计算桶的索引buckets[bucket_index].append(num)# 3. 对每个桶内部进行排序这里使用内置的 Timsortforbucketinbuckets:bucket.sort()# 4. 合并桶sorted_arr[]forbucketinbuckets:sorted_arr.extend(bucket)returnsorted_arr# 测试if__name____main__:arr[0.42,0.32,0.87,0.12,0.95,0.63,0.71,0.29]print(原始数组:,arr)sorted_arrbucket_sort(arr)print(排序后数组:,sorted_arr)输出原始数组: [0.42, 0.32, 0.87, 0.12, 0.95, 0.63, 0.71, 0.29] 排序后数组: [0.12, 0.29, 0.32, 0.42, 0.63, 0.71, 0.87, 0.95]5. 时间复杂度与空间复杂度平均时间复杂度O(n k)n是元素个数k是桶的数量。分桶需要 O(n)桶内排序假设用 O(n log n) 的算法在数据均匀分布时每个桶平均 O(1) 或 O(log n)合并需要 O(n)。当k ≈ n且数据分布均匀时接近O(n)。最坏时间复杂度O(n²)所有元素都落入同一个桶退化为在桶内进行一次完整的排序如插入排序的 O(n²)。空间复杂度O(n k)需要额外的空间存储桶和桶内的元素。6. 优缺点与应用场景优点在数据分布均匀、范围已知时效率极高接近线性。稳定排序如果桶内排序算法稳定。易于并行化处理每个桶的排序可以独立进行。缺点对数据分布敏感如果数据集中在一个桶内效率会大幅下降。需要额外的内存空间。要求数据范围已知且最好是数值型数据。适用场景外部排序数据量太大无法全部加载到内存。数据分布均匀的浮点数排序。年龄、分数等范围有限的整数排序。作为基数排序的子过程。7. 总结桶排序就像生活中的“分类整理”先把物品按类别放入不同的盒子分桶然后在每个盒子里整理排序最后按盒子顺序摆出来合并。它的效率取决于数据分布的均匀程度在理想情况下可以达到惊人的 O(n) 时间复杂度。理解桶排序的关键在于掌握“分桶”的思想这种思想在解决很多计算机问题时都非常有用比如哈希、分治算法。