学号：20021211189 姓名：赵治伟
【嵌牛导读】桶排序（Bucket sort）是计数排序算法的升级版，将数据分到有限数量的桶子里，然后每个桶再分别排序。
【嵌牛鼻子】桶排序算法
【嵌牛正文】
这是一个无序数列：11、38、8、34、27、19、26、13，我们要将它按从小到大排序
先创建5个桶，桶的区间跨度=(最大值-最小值)/桶的数量，注意，每个桶的范围都是包含最小值，不包含最大值，最后一个桶，既包含最小值，也包含最大值
遍历原始序列，将序列放入桶中
每个桶内部的元素分别排序
遍历所有桶，将桶中元素依次输出：8、11、13、19、26、27、34、38
此时，元素已是有序的了
// 冒泡排序，桶内元素排序时使用到
function bubbleSort(arr) {
let length = arr.length;
// 优化2，记录无序数列的边界，每次比较只需要比到这里为止
let lastExchangeIndex = 0;
let sortBorder = length - 1;
for (let i = 0; i < length - 1; i++) {
// 优化1，isSorted判断是否有序，已经有序，不需要再继续交换
let isSorted = true;
for (let j = 0; j < sortBorder; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
isSorted = false;
lastExchangeIndex = j;
}
}
sortBorder = lastExchangeIndex;
if (isSorted) {
break;
}
}
}
// 桶排序
function sort(arr) {
// 得到数列的最大值、最小值，并计算差值d
let max = arr[0];
let min = arr[0];
for (let item of arr) {
if (item > max) {
max = item;
}
if (item < min) {
min = item;
}
}
let d = max - min;
// 初始化桶
let bucketNum = 5;
let bucketArr = [];
for (let i = 0; i < bucketNum; i++) {
bucketArr.push([]);
}
// 遍历原始数组，将原始放入桶中
for (let item of arr) {
let index = parseInt((item - min) * bucketNum / d);
if (index === bucketNum) {
index--;
}
bucketArr[index].push(item);
}
// 对每个桶进行排序，这里用了冒泡排序法
for (let itemArr of bucketArr) {
bubbleSort(itemArr);
}
// 遍历桶，得到排序后结果
let index = 0;
let sortArr = [];
for (let itemArr of bucketArr) {
for (let item of itemArr) {
sortArr[index++] = item;
}
}
return sortArr;
}
let arr = [11, 38, 8, 34, 27, 19, 26, 13];
let sortArr = sort(arr);
console.log(sortArr);
桶排序算法遍历了2次原始数组，运算量为2N，最后，遍历桶输出排序结果的运算量为N，初始化桶的运算量为M。
对桶进行排序，不同的排序算法算法复杂度不同，冒泡排序算法复杂度为O(N^2)，堆排序、归并排序算法复杂度为O(NlogN)，我们以排序算法复杂度为O(NlogN)进行计算，运算量为N/M*log(N/M)*M
最终的运算量为3N+M+N/M*log(N/M)*M，即3N+M+N(logN-logM)，去掉系数，时间复杂度为O(N+M+N(logN-logM))
桶排序算法排序过程中新建了一个桶和一个输出数组，所以算法的空间复杂度是O(N+M)
桶排序算法在对每个桶进行排序时，选择稳定的排序算法，则排序后，相同元素的位置不会发生改变，所以桶排序算法是一种稳定的排序算法
网友评论