摘要:桶排序方法一每個桶只放相同的數字入桶過程把正數和存入正數桶,把負數存入負數桶把數組中的每項作為正數桶或負數桶的下標存入到對應的里出桶過程先遍歷正數桶或負數桶,因為桶里每項都是數組,在遍歷每項正數桶負數桶最終結果負數的絕對值存儲正數桶或負數桶
桶排序:
方法一:每個桶只放相同的數字
入桶過程:
1、 把正數和0存入正數桶,把負數存入負數桶;
2、 把數組中的每項作為正數桶或負數桶的下標存入到對應的key里;
出桶過程:
先遍歷正數桶或負數桶,因為桶里每項都是數組,在遍歷每項
function bucketSort(array){ var bucket = [], //正數桶 negativeBucket = [], //負數桶 result = [], //最終結果 abs, //負數的絕對值 k //存儲正數桶或負數桶每項的length //入桶 for(var i = 0; i < array.length; i++){ if(array[i] < 0){ abs = Math.abs(array[i]) if(!negativeBucket[abs]){ negativeBucket[abs] = [] } negativeBucket[abs].push(array[i]) }else{ if(!bucket[array[i]]){ bucket[array[i]] = [] } bucket[array[i]].push(array[i]) } } //出桶 var l = negativeBucket.length for(var i = l - 1; i >= 0; i --){ //遍歷負數桶,和正數桶正好相反 if(negativeBucket[i]){ k = negativeBucket[i].length for(var j = 0; j < k; j++){ result.push(negativeBucket[i][j]) } } } for(var i = 0; i < bucket.length; i++){ //遍歷正數桶 if(bucket[i]){ k = bucket[i].length for(var j = 0; j < k; j++){ result.push(bucket[i][j]) } } } return result } var a = [1,23,5,6,7,-6,-9,-11,0,-1,-55,-4,7,4,1,222,3,7] bucketSort(a)
方法二:每個桶放一個范圍的數
function bucketSort(array, step) { var result = [], //存儲最終結果 bucket = [], //要用到的桶的數組 bucketCount, //桶的數量 l = array.length, i, j, k, s, max = array[0],//最大數 min = array[0],//最小數 temp; //找出 array 中最大數和最小數 for (i = 1; i < l; i++) { if (array[i] > max) { max = array[i] } if (array[i] < min) { min = array[i]; } } min = min - 1; //如果 array 中有 4 個數,定義每個桶放 2 個數,那只要 2 個桶就夠了,最后結果會少一個數,最小數上 -1,需要的桶就會變成 3 個 bucketCount = Math.ceil((max - min) / step); // 需要桶的數量,和 bucket.length相等 console.log(bucketCount) for (i = 0; i < l; i++) { temp = array[i]; for (j = 0; j < bucketCount; j++) { if (temp > (min + step * j) && temp <= (min + step * (j + 1))) { // 判斷放入哪個桶 /* | j | min + step * j | min + step * (j + 1) | | 0 | -2 | 0 | | 1 | 0 | 2 | | 2 | 2 | 4 | temp 取值 3,-1,0 j 取值 0,1,2 當 i = 0 時,temp = 3,只有 j = 2 能進來; 當 i = 1 時,temp = -1,只有 j = 0 能進來; 當 i = 2 時,temp = 0,只有 j = 0 能進來 */ //bucket 是桶的數組,把每個桶變成數組 //這里 j 的取值順序是 2、1、0,取到的值是 2、0、0 if (!bucket[j]) { bucket[j] = []; } // 通過插入排序將數字插入到桶中的合適位置 s = bucket[j].length; //前兩次 s 是 0,第三次 s 為 1 if (s > 0) { //第三次走這邊 for (k = s - 1; k >= 0; k--) { if (bucket[j][k] > temp) { bucket[j][k + 1] = bucket[j][k]; } else { break; } } bucket[j][k + 1] = temp; //這里 j 取值 0,也就是說放入第一個桶,k + 1 往后放 }else if(s <= 0) { //前兩次走這邊 bucket 中 key 為 0,2有值了 bucket[j].push(temp); } } } } for (i = 0; i < bucketCount; i++) { // 循環取出桶中數據 if (bucket[i]) { k = bucket[i].length; for (j = 0; j < k; j++) { result.push(bucket[i][j]); } } } return result; } var a = [-3,-1,0] bucketSort(a)基數排序
排序過程:準備 0-9 號十個桶
第一次循環:
入桶:按個位數排序,依次放入0-9號桶內
出桶:從 0 號桶依次開始,按先入先出的方式出桶
第二次循環
入桶:按十位數排序,依次放入0-9號桶內,位數不夠的補 0
出桶:從 0 號桶依次開始,按先入先出的方式出桶
第三次按百位排序... 第四次按千位排序...
直到全部排完
function radixSort(array){ var bucket = [], i, max = array[0]; for(i = 1; i < array.length; i++){ if(array[i] > max){ max = array[i] } } for(i = 0; i < 10; i++){ bucket[i] = [] } var loop = (max + "").length for(i = 0; i < loop; i++){ for(j = 0; j < array.length;j++){ var str = array[j] + "" if(str.length >= i + 1){ var k = str[str.length - i - 1] //找出對應位數,比如 345 這個數,第1次找出個位 5,第2次找出十位數 4,第3次找出百位數 3 bucket[k].push(array[j]) }else{ bucket[0].push(array[j]) } } array.splice(0,array.length) //清空數組 for(j = 0; j < 10; j++){ var t = bucket[j].length for(var g = 0; g < t; g++){ array.push(bucket[j][g]) } bucket[j] = [] //清空桶 } } return array } a=[22,3,33,2,1,777] radixSort(a)
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/96504.html
摘要:之所以把計數排序桶排序基數排序放在一起比較,是因為它們的平均時間復雜度都為。動畫計數排序思想找出待排序的數組中最大和最小的元素。桶排序計數排序能派上用場嗎手機號碼有位,范圍太大,顯然不適合用這兩種排序算法。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 1. 前言 算法為王。 想學好前端,先練好內功,只有內功深厚者...
摘要:涉及的算法有計數排序基數排序桶排序,它們被歸類為非比較排序。計數排序沒有對元素進行比較,只是利用了箱與元素的一一對應關系,根據箱已經排好序的先決條件,解決排序。基數排序,是按照從高位到低位的順序進行分組排序。內部排序也是用基數排序。 一般算法能做到O(logn),已經非常不錯,如果我們排序的對象是純數字,還可以做到驚人的O(n)。涉及的算法有計數排序、基數排序、桶排序,它們被歸類為非比...
摘要:計數排序計數排序就是簡單的桶排序,一個桶代表數組中一個數出現的個數,所以需要一個和數組數字范圍一樣大的輔助數組,一般用在范圍小于的排序,時間復雜度為,空間復雜度為數組的數字范圍。 計數排序 計數排序就是簡單的桶排序,一個桶代表數組中一個數出現的個數,所以需要一個和數組數字范圍一樣大的輔助數組,一般用在范圍小于100的排序,時間復雜度為O(n),空間復雜度為數組的數字范圍。 /** *...
摘要:一冒泡排序算法介紹比較相鄰的兩個元素如果前一個比后一個大,則交換位置。它與冒泡排序的不同之處在于,它會優先比較距離較遠的元素。希爾排序的核心在于間隔序列的設定。作為一種線性時間復雜度的排序,計數排序要求輸入的數據必須是有確定范圍的整數。 一、冒泡排序 算法介紹: 比較相鄰的兩個元素,如果前一個比后一個大,則交換位置。 第一輪把最大的元素放到了最后面。 由于每次排序最后一個都是最大的,...
閱讀 746·2023-04-26 01:30
閱讀 3301·2021-11-24 10:32
閱讀 2179·2021-11-22 14:56
閱讀 1979·2021-11-18 10:07
閱讀 553·2019-08-29 17:14
閱讀 624·2019-08-26 12:21
閱讀 3103·2019-08-26 10:55
閱讀 2940·2019-08-23 18:09