本教程介绍了如何用Java编写Bucket排序程序。桶排序也是一种以O(n)时间运行的线性排序算法之一，类似于Radix排序和Counting排序，使其比以O(n * logn)时间运行的快速排序或者合并排序更快。

存储桶排序对应该在一定范围内均匀分布的数据做出了一些假设。

桶排序算法

桶分类通过将元素分布在不同的桶上而起作用。此处使用的存储桶术语也是一个数组，并且通过使用哈希函数将元素分配到这些存储桶。用于计算哈希值的哈希函数必须遵循以下要求：

• 它返回范围为0..bucket_array_length-1的数组索引
• 它是有序的：如果A [i] <A [j]，则hash(A [i])<hash(A [j])

Bucket排序步骤如下

• 使用哈希函数将元素分配到存储桶数组。如果两个元素具有相同的哈希值，即存在哈希冲突，则将列表与每个存储区数组索引相关联，然后将这些元素追加到与该索引关联的列表中。
• 使用插入排序或者选择排序之类的任何排序技术分别对存储桶进行排序。
• 从上到下合并存储桶以获取排序的数组。

桶排序Java程序

public class BucketSort {
  public static void main(String[] args) {
    int[] arr = {37, 74, 12, 45, 67, 99, 65, 29, 32, 9, 15, 4};
    System.out.println("Original array- " + Arrays.toString(arr));
    bucketSort(arr, 10);
    System.out.println("Sorted array after bucket sort- " + Arrays.toString(arr));
  }
	
  private static void bucketSort(int[] arr, int bucketSize){
    // Create bucket array for storing lists
    List<Integer>[] buckets = new List[bucketSize];
    // Linked list with each bucket array index
    // as there may be hash collision 
    for(int i = 0; i < bucketSize; i++){
      buckets[i] = new LinkedList<>();
    }
    // calculate hash and assign elements to proper bucket
    for(int num : arr){
      buckets[hash(num, bucketSize)].add(num);
    }
    // sort buckets
    for(List<Integer> bucket : buckets){
      Collections.sort(bucket);
    }

    int index = 0;
    // Merge buckets to get sorted array
    for(List<Integer> bucket : buckets){
      for(int num : bucket){
        arr[index++] = num;
      }
    }
  }
    
  // hash function used for element distribution 
  private static int hash(int num, int bucketSize){
    return num/bucketSize;
  }
}

输出量

Original array- [37, 74, 12, 45, 67, 99, 65, 29, 32, 9, 15, 4]
Sorted array after bucket sort- [4, 9, 12, 15, 29, 32, 37, 45, 65, 67, 74, 99]

桶排序的时间和空间的复杂度

存储桶排序的平均时间复杂度为O(n + k)，其中O(k)是创建存储桶数组的时间，O(n)是将输入数组元素放入存储桶所需的时间。还有其他循环也需要花费O(n)时间来迭代数组，但是请注意，O(3n + k)也被视为O(n + k)，因为常量没有用Big O表示法计数。

在存储桶排序k中，存储桶阵列需要额外的空间。此外，还有与每个存储区索引关联的列表，其中存储了总共n个元素，使得列表的总长度等于n。因此，桶分类的空间复杂度为O(n + k)。