前言

桶排序也叫箱排序，工作的原理是将数组分到有限数量的桶里。每个桶再进行排序排序，可能再使用别的排序算法或者是以递归的方式继续使用桶排序进行排序，桶排序是鸽巢排序的一种归纳结果。

当输入在一个范围内均匀分布时，桶排序非常好用。

例如：对范围从0.0到1.0且均匀分布在该范围内的大量浮点数进行排序。

创建桶算法的方法：

1. 创建n个空桶（列表）。
2. 对每个数组元素arr[i]插入bucket[n*array[i]]
3. 使用插入排序对各个桶进行排序
4. 连接所有的排序桶

Java示例：

import java.util.*;
import java.util.Collections;

class GFG {

	// 使用桶排序对大小为 n 的 arr[] 进行排序
	static void bucketSort(float arr[], int n)
	{
		if (n <= 0)
			return;

		// 1) 创建 n 个空桶
		@SuppressWarnings("unchecked")
		Vector<Float>[] buckets = new Vector[n];

		for (int i = 0; i < n; i  ) {
			buckets[i] = new Vector<Float>();
		}

		// 2) 将数组元素放在不同的桶中
		for (int i = 0; i < n; i  ) {
			float idx = arr[i] * n;
			buckets[(int)idx].add(arr[i]);
		}

		// 3) 对单个存储桶进行排序
		for (int i = 0; i < n; i  ) {
			Collections.sort(buckets[i]);
		}

		// 4) 将所有桶连接到 arr[]
		int index = 0;
		for (int i = 0; i < n; i  ) {
			for (int j = 0; j < buckets[i].size(); j  ) {
				arr[index  ] = buckets[i].get(j);
			}
		}
	}

	public static void main(String args[])
	{
		float arr[] = { (float)0.897, (float)0.565,
						(float)0.656, (float)0.1234,
						(float)0.665, (float)0.3434 };

		int n = arr.length;
		bucketSort(arr, n);

		System.out.println("排序后的数组为 ");
		for (float el : arr) {
			System.out.print(el   " ");
		}
	}
}

输出

排序后的数组为
0.1234 0.3434 0.565 0.656 0.665 0.897

性能

时间复杂度： 如果我们假设在桶中插入需要 O(1) 时间，那么上述算法的第 1 步和第 2 步显然需要 O(n) 时间。如果我们使用链表来表示桶，O(1) 很容易实现。第 4 步也需要 O(n) 时间，因为所有桶中都会有 n 个项目。  分析的主要步骤是步骤 3。如果所有数字均匀分布，这一步平均也需要 O(n) 时间。

包含负数的情况

上面的例子是桶排序时在对大于零的数组进行排序，对于包含负数的情况需要用下述的方法解决。

1. 将数组拆分为两部分创建两个空向量 Neg[], Pos[]（分别存正数和负数）通过转换将所有负，元素存储在 Neg[]，变为正数（Neg[i] = -1 * Arr[i]），将所有 ve 存储在 pos[] (pos[i] = Arr[i])
2. 调用函数bucketSortPositive(Pos, pos.size())，调用函数 bucketSortPositive(Neg, Neg.size())，bucketSortPositive(arr[], n)
3. 创建n个空桶（或列表）。
4. 将每个数组元素 arr[i] 插入 bucket[n*array[i]]
5. 使用插入排序对单个桶进行排序。
6. 连接所有排序的桶。

Java示例

import java.util.*;
class GFG
{

// 使用桶排序对大小为 n 的 arr[] 进行排序
static void bucketSort(Vector<Double> arr, int n)
{

	// 1) 创建 n 个空桶
	@SuppressWarnings("unchecked")
	Vector<Double> b[] = new Vector[n];
	for (int i = 0; i < b.length; i  )
	b[i] = new Vector<Double>();

	// 2) 将数组元素放在不同的桶中
	for (int i = 0; i < n; i  )
	{
	int bi = (int)(n*arr.get(i)); // 桶中索引
	b[bi].add(arr.get(i));
	}

	// 3) 对单个存储桶进行排序
	for (int i = 0; i < n; i  )
	Collections.sort(b[i]);

	// 4) 将所有桶连接到 arr[]
	int index = 0;
	arr.clear();
	for (int i = 0; i < n; i  )
	for (int j = 0; j < b[i].size(); j  )
		arr.add(b[i].get(j));
}

// 这个函数主要是把数组一分为二，然后对两个数组调用bucketSort()。 
static void sortMixed(double arr[], int n)
{
	Vector<Double>Neg = new Vector<>();
	Vector<Double>Pos = new Vector<>();

	// 遍历数组元素
	for (int i = 0; i < n; i  )
	{
	if (arr[i] < 0)

		// 通过转换为  ve 元素来存储 -Ve 元素
		Neg.add (-1 * arr[i]) ;
	else

		// 存储  ve 元素
		Pos.add (arr[i]) ;
	}
	bucketSort(Neg, (int)Neg.size());
	bucketSort(Pos, (int)Pos.size());

	// 首先通过转换为 -ve 存储 Neg[] 数组的元素
	for (int i = 0; i < Neg.size(); i  )
	arr[i] = -1 * Neg.get( Neg.size() -1 - i);

	// 排序
	for(int j = Neg.size(); j < n; j  )
	arr[j] = Pos.get(j - Neg.size());
}

public static void main(String[] args)
{
	double arr[] = {-0.897, 0.565, 0.656,
					-0.1234, 0, 0.3434};
	int n = arr.length;
	sortMixed(arr, n);

	System.out.print("排序后的数组： \n");
	for (int i = 0; i < n; i  )
	System.out.print(arr[i]   " ");
}0
}

**输出： **

排序后的数组：
-0.897 -0.1234 0 0.3434 0.565 0.656

这篇好文章是转载于：学新通技术网