桶排序

桶排序规则

设置好k个桶
讲N个数据按照规则放入k个桶中
对每个桶中数据进行排序
对已经排序的桶数据进行汇总

这里需要计算 k

k = (max - min) /m

max: 最大值, min: 最小值， m : 需要设置桶分段数

不如： 0-99 以内若干个数，假设 m =10 即需要分10段，0-9 , 10-19 ….90-99 等10段，那么 65 就分在 60-69 段内

代码如下

Array.prototype.bucketSort = function (bucketSize) {
	const DEFAULTSIZE = 5;
	bucketSize = bucketSize || DEFAULTSIZE;
	let arr = this.slice(0);

	function insertSort(arr) {
		for (var i = 1; i < arr.length; i++) {
			var j = i - 1;
			var num = arr[i];
			while (j >= 0 && arr[j] > num) {
				arr[j + 1] = arr[j];
				j--;
			}
			arr[j + 1] = num;
		}
		return arr;
	}

	var min = arr[0];
	var max = arr[1];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] > max) max = arr[i];
		if (arr[i] < min) min = arr[i];
	}

	const bucketCount = Math.floor((max - min) / bucketSize) + 1;

	var buckets = new Array(bucketCount);
	for (var i = 0; i < buckets.length; i++) buckets[i] = [];

	for (var i = 0; i < arr.length; i++) {
		buckets[Math.floor((arr[i] - min) / bucketSize)].push(arr[i]);
	}

	arr.length = 0;

	for (var i = 0; i < bucketCount; i++) {
		insertSort(buckets[i]);
		for (var j = 0; j < buckets[i].length; j++) {
			arr.push(buckets[i][j]);
		}
	}

	return arr;
};

var a = [
	3, 5, 3, 0, 8, 6, 1, 5, 8, 21, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9,
	7, 4, 0, 2, 6,
];

console.log(a.bucketSort());

桶排序 ​

桶排序规则 ​

代码如下 ​

桶排序

桶排序规则

代码如下