1、排序算法概述

常用的内部排序方法有：交换排序（冒泡排序、快速排序）、选择排序（简单选择排序、堆排序）、插入排序（直接插入排序、希尔排序）、归并排序、基数排序（一关键字、多关键字）。

所需辅助空间最多：归并排序

所需辅助空间最少：堆排序

平均速度最快：快速排序

不稳定：快速排序，希尔排序，堆排序。

选择排序算法的依据：任何排序算法在数据量小的时候基本体现不出来差距。选择依据有：

1.数据的规模 ：当数据规模较小时，选择直接插入排序或冒泡排序。
2.数据的类型 ：如全部是正整数，那么考虑使用桶排序为最优。
3.数据已有的顺序 ：快排是一种不稳定的排序（当然可以改进），对于大部分排好的数据，快排会浪费大量不必要的步骤。

数据量极小，而且已经基本排好序，冒泡是最佳选择。我们说快排好，是指大量随机数据下，快排效果最理想。而不是所有情况。

2、桶排序时空复杂度

最佳时间复杂度O(n + k)，最差时间复杂度O(n ^ 2)，平均时间复杂度O(n + k)，空间复杂度O(n * k)，是一种稳定的排序算法。

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

3、桶排序原理

桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ(n)）。但桶排序并不是比较排序，他不受到O(n log n)下限的影响。

实现逻辑：

设置一个定量的数组当作空桶子。

寻访序列，并且把项目一个一个放到对应的桶子去。

对每个不是空的桶子进行排序。

从不是空的桶子里把项目再放回原来的序列中。

4、桶排序思想

桶排序的思想近乎彻底的分治思想。

设置若干个桶，依次扫描待排序的记录R[0]，R[1]，…，R[n-1]，把关键字在某个范围内的记录全都装入到第k个桶里(分配)，然后按序号依次将各非空的桶首尾连接起来(收集)。

例如，要将一副混洗的52张扑克牌按点数A<2<…<J<Q<K排序，需设置13个“桶”，排序时依次将每张牌按点数放入相应的桶里，然后依次将这些桶首尾相接，就得到了按点数递增序排列的一副牌。

桶排序中，桶的个数取决于关键字的取值范围。因此桶排序要求关键字的类型是有限类型，否则可能要无限个桶。

一般情况下每个桶中存放多少个关键字相同的记录是无法预料的，故桶的类型应设计成链表为宜。
为保证排序是稳定的，分配过程中装箱及收集过程中的连接必须按先进先出原则进行。
对于桶排序来说，分配过程的时间是O(n)；收集过程的时间为O(m)（采用链表来存储输入的待排序记录）或O(m+n)。因此，桶排序的时间为O(m+n)。若桶个数m的数量级为O(n)，则桶排序的时间是线性的，即O(n)。

桶排序的缺点：

首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到m-1，那就需要m个桶，这个桶数组就要至少m个空间。其次待排序的元素都要在一定的范围内等等。

桶排序中很重要的一步就是桶的设定了，我们必须根据输入元素的情况，选择一个恰当的 “getBucketIndex” 算法，使得输入元素能够正确的放入对应的桶内，且保证输入数据能够尽量均匀的放入不同的桶内。最糟糕的情况下，即所有的数据都放入了一个桶内，桶内自排序算法为插入排序，那么其时间复杂度就为 O(n ^ 2) 了。

其次，我们可以发现，区间划分的越细，即桶的数量越多，理论上分到每个桶中的元素就越少，桶内数据的排序就越简单，其时间复杂度就越接近于线性。极端情况下，就是区间小到只有1，即桶内只存放一种元素，桶内的元素不再需要排序，因为它们都是相同的元素，这时桶排序差不多就和计数排序一样了。

为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量

使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

5、桶排序举例说明

设有数组 array = [63, 157, 189, 51, 101, 47, 141, 121, 157, 156, 194, 117, 98, 139, 67, 133, 181, 13, 28, 109]，对其进行桶排序：

6、桶排序代码

public class BucketSort {

	public static void main(String[] args) {
		// 输入元素均在 [0, 10) 这个区间内
		float[] arr = new float[] { 0.12f, 2.2f, 8.8f, 7.6f, 7.2f, 6.3f, 9.0f, 1.6f, 5.6f, 2.4f };
		System.out.println("排序前的数组："+Arrays.toString(arr));
		bucketSort(arr);
		System.out.println("排序后的数组："+Arrays.toString(arr));
	}

	public static void bucketSort(float[] arr) {
		// 新建一个桶的集合
		ArrayList<LinkedList<Float>> buckets = new ArrayList<LinkedList<Float>>();
		for (int i = 0; i < 10; i++) {
			// 新建一个桶，并将其添加到桶的集合中去。
			// 由于桶内元素会频繁的插入，所以选择 LinkedList 作为桶的数据结构
			buckets.add(new LinkedList<Float>());
		}
		// 将输入数据全部放入桶中并完成排序
		for (float data : arr) {
			int index = getBucketIndex(data);
			insertSort(buckets.get(index), data);
		}
		// 将桶中元素全部取出来并放入 arr 中输出
		int index = 0;
		for (LinkedList<Float> bucket : buckets) {
			for (Float data : bucket) {
				arr[index++] = data;
			}
		}
	}

	/**
	 * 计算得到输入元素应该放到哪个桶内
	 */
	public static int getBucketIndex(float data) {
		// 这里例子写的比较简单，仅使用浮点数的整数部分作为其桶的索引值
		// 实际开发中需要根据场景具体设计
		return (int) data;
	}

	/**
	 * 我们选择插入排序作为桶内元素排序的方法 每当有一个新元素到来时，我们都调用该方法将其插入到恰当的位置
	 */
	public static void insertSort(List<Float> bucket, float data) {
		ListIterator<Float> it = bucket.listIterator();
		boolean insertFlag = true;
		while (it.hasNext()) {
			if (data <= it.next()) {
				it.previous(); // 把迭代器的位置偏移回上一个位置
				it.add(data); // 把数据插入到迭代器的当前位置
				insertFlag = false;
				break;
			}
		}
		if (insertFlag) {
			bucket.add(data); // 否则把数据插入到链表末端
		}
	}
}

// 排序前的数组：[0.12, 2.2, 8.8, 7.6, 7.2, 6.3, 9.0, 1.6, 5.6, 2.4]
// 排序后的数组：[0.12, 1.6, 2.2, 2.4, 5.6, 6.3, 7.2, 7.6, 8.8, 9.0]

目录CONTENT

java排序算法之桶排序