桶排序是一种排序算法，它将未排序的数组元素分成称为桶的若干组。然后通过使用任何合适的排序算法或递归应用相同的存储桶算法对每个存储桶进行排序。最后，将排序后的桶组合起来形成最终的排序数组。

分散聚集方法
桶排序的过程可以理解为一种分散-聚集的方法。在这里，首先将元素分散到桶中，然后对每个桶中的元素进行排序。最后，按顺序收集元素。


桶排序的工作

算法的图解

假设，输入数组是 | | | —- | | 输入数组 |

创建一个大小为 10 的数组。这个数组的每个槽都用作存储元素的桶。


每个位置都是一个桶的数组

将元素从数组插入到桶中。根据桶的范围插入元素。

在我们的示例代码中，我们有桶，每个范围从 0 到 1、1 到 2、2 到 3、…… (n-1) 到 n。
假设，一个输入元素是 0.23 被采用。它乘以 size = 10（即 .23*10=2.3）。然后，将其转换为整数（即 2.3≈2）。最后，0.23 被插入到bucket-2 中。 | 桶排序（Bucket Sort） - 图4 | | —- | | 将数组中的所有元素插入桶中 |

同样，0.25 也被插入到同一个桶中。每次取浮点数的下限值。如果我们将整数作为输入，我们必须将其除以区间（此处为 10）以获得下限值。类似地，其他元素被插入到它们各自的桶中。


将数组中的所有元素插入桶中

每个桶的元素使用任何稳定的排序算法进行排序。在这里，我们使用了快速排序（内置功能）。 | | | —- | | 对每个桶中的元素进行排序 |
收集每个桶中的元素。

算法的伪码

bucketSort()
  create N buckets each of which can hold a range of values
  for all the buckets
    initialize each bucket with 0 values
  for all the buckets
    put elements into buckets matching the range
  for all the buckets 
    sort elements in each bucket
  gather elements from each bucket
end bucketSort

算法的实现

// Bucket sort in Java

import java.util.ArrayList;
import java.util.Collections;

public class BucketSort {
  public void bucketSort(float[] arr, int n) {
    if (n <= 0)
      return;
    @SuppressWarnings("unchecked")
    ArrayList<Float>[] bucket = new ArrayList[n];

    // Create empty buckets
    for (int i = 0; i < n; i++)
      bucket[i] = new ArrayList<Float>();

    // Add elements into the buckets
    for (int i = 0; i < n; i++) {
      int bucketIndex = (int) arr[i] * n;
      bucket[bucketIndex].add(arr[i]);
    }

    // Sort the elements of each bucket
    for (int i = 0; i < n; i++) {
      Collections.sort((bucket[i]));
    }

    // Get the sorted array
    int index = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0, size = bucket[i].size(); j < size; j++) {
        arr[index++] = bucket[i].get(j);
      }
    }
  }

  // Driver code
  public static void main(String[] args) {
    BucketSort b = new BucketSort();
    float[] arr = { (float) 0.42, (float) 0.32, (float) 0.33, (float) 0.52, (float) 0.37, (float) 0.47,
        (float) 0.51 };
    b.bucketSort(arr, 7);

    for (float i : arr)
      System.out.print(i + "  ");
  }
}

算法复杂性

时间复杂度
最好的	O(n+k)
最差	O(n2)
平均	O(n)
空间复杂度	O(n+k)
稳定	Yes

最坏情况复杂度： O(n2)

当数组中有近距离元素时，它们很可能被放在同一个桶中。这可能会导致某些桶的元素数量多于其他桶。它使复杂性取决于用于对桶的元素进行排序的排序算法。当元素的顺序相反时，复杂性变得更糟。如果使用插入排序对桶的元素进行排序，则时间复杂度变为。

最佳情况复杂度： O(n+k)
当元素均匀分布在桶中且每个桶中的元素数量几乎相等时，就会发生这种情况。如果桶内的元素已经排序，复杂性会变得更好。如果使用插入排序对桶的元素进行排序，那么最好情况下的整体复杂性将是线性的，即O(n+k). O(n)是制作桶O(k)的复杂度，是在最佳情况下使用具有线性时间复杂度的算法对桶的元素进行排序的复杂度。
平均情况复杂度： O(n)
当元素在数组中随机分布时发生。即使元素分布不均匀，桶排序也会在线性时间内运行。直到桶大小的平方和与元素总数成线性关系，它才成立。

桶排序应用

桶排序在以下情况下使用：

输入均匀分布在一个范围内。
有浮点值

相似的算法

冒泡排序
快速排序
插入排序
归并排序
选择排序