溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章給大家分享的是有關JS如何實現桶排的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。
桶排序，利用編號分組存儲數字，再利用編號合并分組的一種算法排序。
舉個易于理解的例子：
一組數字，9,3,4,0,2,8,5,1,7,6,11,10,18,15,17,12,16,13,19,14
我們把這組數字分組編號成10個桶裝起來，但怎么編號分組呢？
這里我們利用數字范圍來對數字進行分桶。首先，最大數減去最小數，獲取這組數字的取值范圍，然后，我們讓這個取值范圍除以桶數，獲取一個桶的取值范圍，既然知道一個桶的取值范圍，那么，通過對比每個數字占用多少個桶，我們就可以獲取這個數字所對應的桶的編號了。（換一句話說，就是每個數字占用多少個取值范圍，這里的桶其實就是數字的取值范圍的具體化東西）
利用上面的例子做解釋：
上面的最大值是19，最小值是0，所以這組數的取值范圍是：19-0=19。
我們要用10個桶來分裝這組數字，則一個桶的取值范圍是：19 / 10 = 1.9。
所以，一個桶的取值范圍就是：1.9。
知道了這些之后，我們怎么知道每個數字所對應的桶的編號呢？
我們讓每個數字減去最小值再除以一個桶的取值范圍就可以獲得這個數字所對應的桶編號了，為什么這么說呢？因為我們就是利用數值范圍來分桶的，所以理所當然的也是獲取每個數字的取值范圍來分桶的編號，而最小值就是我們的取值標準，當然是要每個數字都減去它才能準確的獲取每個數的取值范圍了。
根據上面的解釋，那么，第一個數字的桶編號就是：(9-0) / 1.9 = 4.7368·······
當然為了確保編號為整數，我們必須給編號取整，這里我們是向上取整，所以第一個數：9的桶編號就是5啦。
其他的數字獲取桶編號都是同樣的原理，這里就不再重復敘述了。
下面是js程序的實現：
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="zh-cn">
<head>
<meta http-equiv="Content-Type" content="text/html;charset=UTF-8" />
<title>桶排序</title>
<meta name="keywords" content="關鍵字列表" />
<meta name="description" content="網頁描述" />
<link rel="stylesheet" type="text/css" href="" />
<style type="text/css"></style>
<script type="text/javascript">
//桶排序,參數數組,桶的個數，這里用數組模擬桶
var cask=function (arr,caskCount){
//不是數組，返回false
if(toString.call(arr) != '[object Array]'){
return false;
}
//獲取數組的長度
var len = arr.length;
if(len <=1){
return arr;//長度小于等于1不用排序
}
var list = [],//裝桶的桶，用它來控制存儲桶的編號
result = [],//返回的結果
max = arr[0],
min = arr[0];
//默認桶的個數為10
var caskCount = parseInt(caskCount) > 0 ? parseInt(caskCount) : 10;
//獲取數組的最大值和最小值
for(var i=1;i<len-1;i++){
max = arr[i] <= max ? max : arr[i] ;
min = arr[i] >= min ? min : arr[i] ;
}
//分成caskCount個桶，桶所占用的范圍
var range = (max - min) / caskCount;
for(var i=0;i<len;i++){
//桶的數值減去最小數 min 獲取的是桶占用的范圍，再除以一個桶的范圍，就是獲取對應的桶編號
var index = Math.floor((arr[i] - min) / range);
//桶里是否有值，有值則進行排序
if(list[index]){//用數組模擬桶
//獲取桶最后一個值的下標
var k=list[index].length - 1;
//桶最后的值大于要插進來的值，所以要把這個值插到桶的前面去，但不知道這個值要插入到前面的哪個位置，所以，就只能對比排序了
//對桶進行排序
while(k >=0 && list[index][k] > arr[i]){
//桶前面的數字放到后面去
list[index][k+1] = list[index][k];//第一個k+1為新增的桶
//小的提前一個位置
//list[index][k] = arr[i];
k--;
}
//不用排序的，直接加在桶的最后面
list[index][k+1] = arr[i];
}else{
//沒有值則生成桶，并把值放到對應的桶中
list[index]=[];
list[index][0]=arr[i];
}
}
//合并桶
var n=0;
while(n <= caskCount){
if(list[n]){
result = result.concat(list[n]);
}
n++;
}
return result;
}
var arr=[8,39,400,500,3,4,20,44,440];
alert(cask(arr,10));
//alert(parseInt(-1) ? parseInt(-1) : 1);
</script>
</head>
<body>
</body>
</html>感謝各位的閱讀！關于“JS如何實現桶排”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
