一、原地算法

在談sort之前，我們先了解一下原地算法，什么事原地算法呢？所謂原地算法就是說基于原有的數(shù)據(jù)結(jié)構(gòu)進(jìn)行一定的操作修改，而不借助額外的空間。使用原地算法時，其內(nèi)存干凈，空間復(fù)雜度是O(1)，可以減少沒必要的內(nèi)存，避免造成內(nèi)存浪費和冗余。當(dāng)然，減小內(nèi)存損耗會帶來算法復(fù)雜度和時間消耗的增加，所以是一個Tradeoff。Tradeoff 是一種針對目標(biāo)選擇有效的路徑的思維方式，需要對做的事情權(quán)衡利弊，選擇最佳方式處理問題。

二、Array.property.sort（）

含義：sort方法基于原地算法實現(xiàn)數(shù)組排序，直接對數(shù)據(jù)進(jìn)行排序

參數(shù)：sort(compare(a,b))，指定順序?qū)?shù)組進(jìn)行排序，不寫參數(shù)的時候，默認(rèn)會將原數(shù)據(jù)轉(zhuǎn)換成字符串按照字符的Unicode編碼進(jìn)行排序。

compare(a,b)中，a、b都是比較參數(shù)，當(dāng)
a-b>0 ，交換位置
a-b=0，位置不變
a-b<0，位置不變

隨機排序我們都會想到Math的random方法，具體實現(xiàn)如下，但是這樣操作確有缺陷，理論很豐滿，實踐很殘酷。

1、方法一（不推薦）

arr.sort(() => Math.random() - 0.5)

缺陷：chrome瀏覽器對于數(shù)組長度為10以內(nèi)的使用插入排序，反之則為快速排序和插入排序的組合，故而并不能做到隨機分布。測試：測試某數(shù)據(jù)在數(shù)組中各個位置的次數(shù)。

        let obj = {};
		let count = 0;
		let n = 10000;
		while (n--) {
			let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14]
			arr.sort(() => Math.random() - 0.5)
			let index = arr.indexOf(1)//取1在數(shù)組排序后的位置
			obj[index] ? obj[index]++ : obj[index] = 1
		}

輸出：

圖示：

ECMAScript中關(guān)于Array.prototype.sort(comparefn)的標(biāo)準(zhǔn)，其中并沒有規(guī)定具體的實現(xiàn)算法，但是提到一點： Calling comparefn(a,b) always returns the same value v when given a specific pair of values a and b as its two arguments.也就是說，對同一組a、b的值，comparefn(a, b)需要總是返回相同的值。而上面的() => Math.random() -0.5（即(a, b) => Math.random() - 0.5）顯然不滿足這個條件。 翻看v8引擎數(shù)組部分的源碼，注意到它出于對性能的考慮，對短數(shù)組（例如長度小于10）使用的是插入排序，對長數(shù)組則使用了快速排序。

理解：(a, b) => Math.random() - 0.5，每次a，b都是固定的，但是Math.random() - 0.5）卻是隨機的，

2、方法一改良

構(gòu)造一個新數(shù)組，如[{v:1,k:Math.random()},{v:1,k:Math.random()}]，具體如下：

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14]
for(let i=0;i<arr.length;i++){
    shuffle(arr)
}
function shuffle(arr){
   let newArr = arr.map(item=>({v:i,k:Math.random())})
   newArr.sort((a,b)=> (a.k - b.k))
   arr.splice(0, arr.length, ...newArr.map(i => i.v));
}

三、洗牌算法實現(xiàn)隨機排序

1、換牌

邏輯：從一副牌中抽取一張，與最后一張牌進(jìn)行交換，放到最后證明該牌已經(jīng)被隨機抽選過，而被交換的牌就排在前面，就有機會被繼續(xù)抽選。

• 隨機抽取一張
• 抽取的放置到最后位置
• 最后位置的牌放置在隨機抽取的位置

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14];
funtion shuffle(ar){
   for(let i = arr.length;i>0;i--){
      let temRandom =  Math.floor(Math.random()*i)
      arr[i] = arr[temRandom];
      arr[temRandom] = arr[i]
   }
   return arr
}
shuffle(arr)

2、抽牌

邏輯：從一副牌抽取一張放置一旁，則這幅牌會越抽越少，直至到最后一張。

• 隨機抽取一張
• 抽取的牌放置旁邊
• 在抽取的那副牌沖除去隨機抽取的那張牌

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14];
funtion shuffle(ar){
   let temp = [];
   for(let i = arr.length;i>0;i--){
      let temRandom =  Math.floor(Math.random()*i)
      temp.push(arr[temRandom])
      arr.splice(temRandom,1)//抽取一張后，要除去這張牌，然后在剩下的牌中繼續(xù)抽
   }
   return temp
}
shuffle(arr)

附：本文用到的JS基礎(chǔ)

本文用到數(shù)組方法基本介紹

splice返回被刪除的元素，直接修改數(shù)組數(shù)據(jù)，可接受1/2/3個參數(shù)

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14];
arr.splice(0)//刪除索引從0開始的所有數(shù)據(jù)，即刪除所有數(shù)據(jù)
arr.splice(0)//刪除索引從1開始的所有數(shù)據(jù)，即只保留第一位數(shù)據(jù)
arr.splice(2,1)//刪除索引為2的數(shù)據(jù)
arr.splice(0,arr.length,5)//刪除原數(shù)組的數(shù)據(jù)，并把數(shù)據(jù)5填充到arr中

• Math.floor() 向下取整
• Math.ceil() 向上取整

總結(jié)

到此這篇關(guān)于JS中數(shù)組隨機排序?qū)崿F(xiàn)方法的文章就介紹到這了,更多相關(guān)JS數(shù)組隨機排序?qū)崿F(xiàn)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論