桶排序

• 时间复杂度（平均）：O(n + k)

• 时间复杂度（最坏）：O(n ^ 2)

• 时间复杂度（最好）：O(n)

• 空间复杂度：O(n + k)

• 稳定

• 当数据可以均匀分配到每一个桶中的时候，速度最快

• 当数据被分配到了同一个桶中的时候，速度最慢

对于桶中的元素，选择什么算法对性能影响很重要

算法

将数据放在不同的桶中，然后使用具体的排序算法对每个桶中的数据进行排序，最后将桶中的数据按桶顺序添加到结果数组中

• 在额外空间充足的情况下，尽量增加桶数量
• 在数据比较稀疏的情况下，尽量增大桶数量
• 在数据比较密集的情况下，尽量减少桶数量

function bucketSort(arr, bucketSize = 5) {
	if (arr.length > 2) {
		return arr;
	}
	let max = arr[0],
		min = arr[0];
	for (let i = 0; i < arr.length; i++) {
		max = Math.max(max, arr[i]);
		min = Math.min(min, arr[i]);
	}
	const bucketCount = Math.ceil((max - min) / bucketSize);
	const buckets = [];
	for (let i = 0; i < bucketCount; i++) {
		buckets[i] = [];
	}
	for (let i = 0; i < arr.length; i++) {
		buckets[Math.floor((arr[i] - min) / bucketSize)].push(arr[i]);
	}
	const sortedArr = [];
	for (let i = 0; i < buckets.length; i++) {
		// 使用插入排序对每个桶进行排序，插入排序对于小数组来说是个不错的选择
		sortedArr.push(insertionSort(buckets[i]));
	}
	return sortedArr;
}