桶排序（Bucket Sort） 桶排序是一种线性时间复杂度的排序算法，适用于数据分布均匀且范围已知的情况。它的核心思想是将数据分到有限数量的桶里，每个桶再分别排序（通常使用其他排序算法），最后按顺序合并各个桶的结果。 基本思想与适用条件 数据需要均匀分布在某个范围内，这样才能保证分桶后每个桶的数据量相对均衡 需要知道数据的范围，比如[ min, max ] 是一种分布式排序算法，将数据分散到多个"桶"中处理 算法步骤详解 确定桶的数量和范围 假设有n个元素待排序，数据范围是[ min, max ] 通常设置桶的数量为n或根据数据分布确定 每个桶的负责范围 = (max - min) / 桶的数量 数据分桶 遍历每个元素，根据其值计算应该放入哪个桶 计算桶索引的公式：index = (value - min) * n / (max - min + 1) 将元素放入对应的桶中 每个桶内部排序 对每个非空桶中的元素进行排序 可以使用插入排序、快速排序等算法 如果数据分布均匀，每个桶的元素数量较少，插入排序效率很好 合并结果 按照桶的顺序（从0到n-1） 依次将每个桶中的有序元素取出 合并成一个完整的有序序列 具体示例演示 假设要对数组[ 0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]排序，范围[ 0,1 ] 初始化 ：创建10个桶（因为n=10），每个桶范围0.1 分桶 ： 桶0[ 0.0-0.1 ]：无 桶1[ 0.1-0.2 ]：0.17, 0.12 桶2[ 0.2-0.3 ]：0.26, 0.21, 0.23 桶3[ 0.3-0.4 ]：0.39 桶4[ 0.4-0.5 ]：无 桶5[ 0.5-0.6 ]：无 桶6[ 0.6-0.7 ]：0.68 桶7[ 0.7-0.8 ]：0.78, 0.72 桶8[ 0.8-0.9 ]：无 桶9[ 0.9-1.0 ]：0.94 桶内排序 ：每个桶分别排序 合并 ：按桶顺序输出得到有序序列 时间复杂度分析 最好情况：O(n) - 数据均匀分布，每个桶元素数量接近 平均情况：O(n + k)，其中k是桶的数量 最坏情况：O(n²) - 所有数据集中在一个桶中 空间复杂度 ：O(n + k)，需要额外的桶存储空间 优缺点总结 优点：在数据分布均匀时效率很高，稳定排序 缺点：对数据分布有要求，需要知道数据范围，空间开销较大 桶排序特别适合外部排序和处理海量数据，在实际应用中经常与其他排序算法结合使用。