排序算法-桶排序

桶排序的基础

桶排序的定义：假定：输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数。将区间[0, 1)划分为n个大小相等的子区间（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…将n个输入元素分配到这些桶中，对桶中元素进行排序，然后依次连接桶输入0 ≤A[1..n] <1辅助数组B[0..n-1]是一指针数组，指向桶（链表）。
桶排序的说明：桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（O(n)）。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。

桶排序的步骤

1. 找出排序数组 arr 中最小值min和最大值max，并设定用来排序的桶的数量 N。
2. 计算出每个桶中的数据范围为 L = (max - min)/N。
3. 再计算出 N 个桶的数值范围，如第一个桶[min, min + L),第二个桶[min + L, min + 2L),依次类推…
4. 将数组arr分配到相应的桶中，再在每个桶的数据进行排序（一般插入排序就可）。
5. 将桶中的数据依次取出放入新数组，这时新数组就是排好序的数组了。

代码实现

// 插入排序
function insertionSort(arr) {
	var len = arr.length;
	var preIndex, current;
	for (var i = 1; i < len; i++) {
		preIndex = i - 1;
		current = arr[i];
		while(preIndex >= 0 && arr[preIndex] > current) {
			arr[preIndex+1] = arr[preIndex];
			preIndex--;
		}
		arr[preIndex+1] = current;
	}
	return arr;
}

// 桶排序
function bucketSort(array, bucketSize) {
	let arr = array.slice();
	let i;
	let minValue = arr[0];
	let maxValue = arr[0];

	// 空数组时直接返回空数组
	if (arr.length === 0) {
	  return arr;
	}

	
	for (i = 1; i < arr.length; i++) {
	  if (arr[i] < minValue) {
		  minValue = arr[i];                //输入数据的最小值
	  } else if (arr[i] > maxValue) {
		  maxValue = arr[i];                //输入数据的最大值
	  }
	}

	// 桶的初始化
	let DEFAULT_BUCKET_SIZE = 5;            //设置桶的默认数量为5
	bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
	let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;   
	let buckets = new Array(bucketCount);

	// 二维数组，每个桶初始化为空数组
	for (i = 0; i < buckets.length; i++) {
		buckets[i] = [];
	}

	// 利用映射函数将数据分配到各个桶中
	for (i = 0; i < arr.length; i++) {
		buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
	}

	arr.length = 0;
	for (i = 0; i < buckets.length; i++) {
		insertionSort(buckets[i]);                      //对每个桶进行插入排序
		for (var j = 0; j < buckets[i].length; j++) {
			arr.push(buckets[i][j]);                      
		}
	}

	return arr;
}

let arr = [63,157,189,51,101,47,141,121,157,156,194,117,98,139,67,133,181,13,28,109];
var demo = bucketSort(arr, 4); // 这里我分配了4个桶，桶越多越快但需要的内存就越多
console.log(arr); // [63, 157, 189, 51, 101, 47, 141, 121, 157, 156, 194, 117, 98, 139, 67, 133, 181, 13, 28, 109]
console.log(demo); // [13, 28, 47, 51, 63, 67, 98, 101, 109, 117, 121, 133, 139, 141, 156, 157, 157, 181, 189, 194]

PS：桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
为了使桶排序更加高效，我们需要做到这两点：

1. 在额外空间充足的情况下，尽量增大桶的数量
2. 使用的映射函数能够将输入的N个数据均匀的分配到K个桶中
   同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
   什么时候最快（Best Cases）：
   当输入的数据可以均匀的分配到每一个桶中
   什么时候最慢（Worst Cases）：
   当输入的数据被分配到了同一个桶中

图片展示

参考文档：
JS的十大经典算法排序
十大经典排序算法
桶排序