一、原地算法

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

二、Array.property.sort（）

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

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

compare(a,b)中，a、b都是比較參數(shù)，當(dāng)

• a-b>0 ，交換位置
• a-b=0，位置不變
• a-b<0，位置不變

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

1、方法一（不推薦）

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

缺陷：chrome瀏覽器對(duì)于數(shù)組長(zhǎng)度為10以?xún)?nèi)的使用插入排序，反之則為快速排序和插入排序的組合，故而并不能做到隨機(jī)分布。

測(cè)試：測(cè)試某數(shù)據(jù)在數(shù)組中各個(gè)位置的次數(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)，其中并沒(méi)有規(guī)定具體的實(shí)現(xiàn)算法，但是提到一點(diǎ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.也就是說(shuō)，對(duì)同一組a、b的值，comparefn(a, b)需要總是返回相同的值。而上面的() => Math.random() -0.5（即(a, b) => Math.random() - 0.5）顯然不滿足這個(gè)條件。 翻看v8引擎數(shù)組部分的源碼，注意到它出于對(duì)性能的考慮，對(duì)短數(shù)組（例如長(zhǎng)度小于10）使用的是插入排序，對(duì)長(zhǎng)數(shù)組則使用了快速排序。

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

2、方法一改良

構(gòu)造一個(gè)新數(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));
}

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

1、換牌

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

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

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、抽牌

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

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

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個(gè)參數(shù)

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14];
arr.splice(0)//刪除索引從0開(kāi)始的所有數(shù)據(jù)，即刪除所有數(shù)據(jù)
arr.splice(0)//刪除索引從1開(kāi)始的所有數(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() 向上取整

到此這篇關(guān)于JavaScript中數(shù)組隨機(jī)排序的實(shí)現(xiàn)詳解的文章就介紹到這了,更多相關(guān)JavaScript數(shù)組隨機(jī)排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論