學(xué)號(hào)：20021211189? ? ? ?姓名：趙治偉
【嵌牛導(dǎo)讀】桶排序（Bucket sort）是計(jì)數(shù)排序算法的升級(jí)版桐经，將數(shù)據(jù)分到有限數(shù)量的桶子里果复，然后每個(gè)桶再分別排序。
【嵌牛鼻子】桶排序算法
【嵌牛正文】
這是一個(gè)無(wú)序數(shù)列：11诱鞠、38、8嫉戚、34棒呛、27、19告唆、26棺弊、13，我們要將它按從小到大排序
先創(chuàng)建5個(gè)桶擒悬，桶的區(qū)間跨度=(最大值-最小值)/桶的數(shù)量模她，注意，每個(gè)桶的范圍都是包含最小值懂牧，不包含最大值侈净，最后一個(gè)桶，既包含最小值僧凤，也包含最大值
遍歷原始序列畜侦，將序列放入桶中
每個(gè)桶內(nèi)部的元素分別排序
遍歷所有桶，將桶中元素依次輸出：8躯保、11旋膳、13、19途事、26验懊、27、34盯孙、38
此時(shí)鲁森，元素已是有序的了
// 冒泡排序，桶內(nèi)元素排序時(shí)使用到
function bubbleSort(arr) {
? ? let length = arr.length;
? ? // 優(yōu)化2振惰，記錄無(wú)序數(shù)列的邊界歌溉，每次比較只需要比到這里為止
? ? let lastExchangeIndex = 0;
? ? let sortBorder = length - 1;
? ? for (let i = 0; i < length - 1; i++) {
? ? ? ? // 優(yōu)化1，isSorted判斷是否有序骑晶，已經(jīng)有序痛垛，不需要再繼續(xù)交換
? ? ? ? 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) {
? ? // 得到數(shù)列的最大值、最小值桶蛔，并計(jì)算差值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([]);
? ? }
? ? // 遍歷原始數(shù)組匙头，將原始放入桶中
? ? for (let item of arr) {
? ? ? ? let index = parseInt((item - min) * bucketNum / d);
? ? ? ? if (index === bucketNum) {
? ? ? ? ? ? index--;
? ? ? ? }
? ? ? ? bucketArr[index].push(item);
? ? }
? ? // 對(duì)每個(gè)桶進(jìn)行排序，這里用了冒泡排序法
? ? for (let itemArr of bucketArr) {
? ? ? ? bubbleSort(itemArr);
? ? }
? ? // 遍歷桶仔雷，得到排序后結(jié)果
? ? 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次原始數(shù)組蹂析，運(yùn)算量為2N舔示，最后，遍歷桶輸出排序結(jié)果的運(yùn)算量為N电抚，初始化桶的運(yùn)算量為M惕稻。
對(duì)桶進(jìn)行排序，不同的排序算法算法復(fù)雜度不同蝙叛，冒泡排序算法復(fù)雜度為O(N^2)俺祠，堆排序、歸并排序算法復(fù)雜度為O(NlogN)借帘，我們以排序算法復(fù)雜度為O(NlogN)進(jìn)行計(jì)算蜘渣，運(yùn)算量為N/M*log(N/M)*M
最終的運(yùn)算量為3N+M+N/M*log(N/M)*M，即3N+M+N(logN-logM)肺然，去掉系數(shù)蔫缸，時(shí)間復(fù)雜度為O(N+M+N(logN-logM))
桶排序算法排序過(guò)程中新建了一個(gè)桶和一個(gè)輸出數(shù)組，所以算法的空間復(fù)雜度是O(N+M)
桶排序算法在對(duì)每個(gè)桶進(jìn)行排序時(shí)际起，選擇穩(wěn)定的排序算法捂龄，則排序后，相同元素的位置不會(huì)發(fā)生改變加叁，所以桶排序算法是一種穩(wěn)定的排序算法
