# 桶排序（Bucket Sort）

URL: https://caijiao.org/sort/9-bucket-sort
Source: docs/sort/9-bucket-sort.md
Description: 桶排序适合数据分布均匀的浮点数或整数场景。本文介绍原理及实现思路，提供 JavaScript、Python、C++、Java、PHP、Go 多语言代码示例，便于学习。

桶排序是将输入数据**分配到有限数量的桶中**，对每个桶内的数据分别进行排序，最后再将所有桶中的数据**按顺序合并**得到最终结果。

它是计数排序的推广，适合**数据均匀分布的浮点数或整数场景**，时间复杂度在理想状态下可达 **O(n)**。

## 📌 算法原理解释

桶排序的基本流程如下：

1. 找到待排序数组的最大值与最小值；
2. 根据范围划分若干个桶；
3. 将每个元素根据其值放入对应的桶中；
4. 对每个桶内部进行排序（可使用插入排序、快排等）；
5. 合并所有桶中的元素得到最终结果。

> 若数据分布不均匀，则性能可能退化为 O(n²)。

## 💻 多语言代码实现


// JavaScript 桶排序（浮点数支持）
function bucketSort(arr, bucketSize = 5) {
  if (arr.length === 0) return [];

  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const bucketCount = Math.floor((max - min) / bucketSize) + 1;
  const buckets = Array.from({ length: bucketCount }, () => []);

  for (let num of arr) {
    const index = Math.floor((num - min) / bucketSize);
    buckets[index].push(num);
  }

  return buckets.flatMap(bucket => bucket.sort((a, b) => a - b));
}
````

```python
# Python 桶排序
def bucket_sort(arr, bucket_size=5):
    if not arr:
        return []
    min_val, max_val = min(arr), max(arr)
    bucket_count = (max_val - min_val) // bucket_size + 1
    buckets = [[] for _ in range(bucket_count)]

    for num in arr:
        index = (num - min_val) // bucket_size
        buckets[index].append(num)

    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(sorted(bucket))
    return sorted_arr
```

```cpp
// C++ 桶排序（使用 vector）
#include <vector>
#include <algorithm>
using namespace std;

vector<float> bucketSort(const vector<float>& arr, int bucketSize = 5) {
    if (arr.empty()) return {};

    float minVal = *min_element(arr.begin(), arr.end());
    float maxVal = *max_element(arr.begin(), arr.end());
    int bucketCount = (maxVal - minVal) / bucketSize + 1;

    vector<vector<float>> buckets(bucketCount);
    for (float num : arr) {
        int index = (num - minVal) / bucketSize;
        buckets[index].push_back(num);
    }

    vector<float> result;
    for (auto& bucket : buckets) {
        sort(bucket.begin(), bucket.end());
        result.insert(result.end(), bucket.begin(), bucket.end());
    }

    return result;
}
```

```java
// Java 桶排序（适用于浮点数）
import java.util.*;

public class BucketSort {
    public static List<Float> bucketSort(List<Float> arr, int bucketSize) {
        if (arr.isEmpty()) return arr;

        float min = Collections.min(arr);
        float max = Collections.max(arr);
        int bucketCount = (int)((max - min) / bucketSize) + 1;

        List<List<Float>> buckets = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) buckets.add(new ArrayList<>());

        for (float num : arr) {
            int index = (int)((num - min) / bucketSize);
            buckets.get(index).add(num);
        }

        List<Float> result = new ArrayList<>();
        for (List<Float> bucket : buckets) {
            Collections.sort(bucket);
            result.addAll(bucket);
        }
        return result;
    }
}
```

```php
<?php
// PHP 桶排序
function bucketSort(array $arr, int $bucketSize = 5): array {
    if (empty($arr)) return [];

    $min = min($arr);
    $max = max($arr);
    $bucketCount = intval(($max - $min) / $bucketSize) + 1;
    $buckets = array_fill(0, $bucketCount, []);

    foreach ($arr as $num) {
        $index = intval(($num - $min) / $bucketSize);
        $buckets[$index][] = $num;
    }

    $result = [];
    foreach ($buckets as $bucket) {
        sort($bucket);
        $result = array_merge($result, $bucket);
    }
    return $result;
}
?>
```

```go
// Go 桶排序
package main

import (
 "sort"
)

func bucketSort(arr []float64, bucketSize int) []float64 {
 if len(arr) == 0 {
  return []float64{}
 }
 min, max := arr[0], arr[0]
 for _, v := range arr {
  if v < min {
   min = v
  }
  if v > max {
   max = v
  }
 }

 bucketCount := int((max - min)/float64(bucketSize)) + 1
 buckets := make([][]float64, bucketCount)
 for _, v := range arr {
  index := int((v - min) / float64(bucketSize))
  buckets[index] = append(buckets[index], v)
 }

 result := []float64{}
 for _, bucket := range buckets {
  sort.Float64s(bucket)
  result = append(result, bucket...)
 }
 return result
}
```


## ✅ 算法特点与总结

| 属性     | 描述                         |
| ------ | -------------------------- |
| 时间复杂度  | 平均 O(n + k)，最坏 O(n²)（桶极不均） |
| 空间复杂度  | O(n + k)（桶空间）              |
| 稳定性    | ✅ 若桶内排序稳定                  |
| 是否原地排序 | ❌ 否（需要桶数组）                 |
| 适用条件   | 数据分布均匀，范围已知或可估计            |

> 📌 提示：桶排序常用于浮点数排序，或对数据分布已知的情况。桶内排序推荐使用插入排序或稳定算法以保持整体稳定性。