數(shù)組隨機(jī)排序：洗牌算法(Fisher–Yates shuffle)

張金寶發(fā)布于2019-08-20 15:27 / 731人閱讀

摘要：代碼實(shí)現(xiàn)代碼一測(cè)試用例輸出其中，代碼二測(cè)試用例輸出其中，參考資料洗牌算法學(xué)習(xí)筆記數(shù)組隨機(jī)排序洗牌算法給數(shù)組隨機(jī)排序洗牌算法原理

原理及步驟

1.定義一個(gè)數(shù)組（shuffled），長(zhǎng)度（length）是原數(shù)組（arr）長(zhǎng)度
2.取 0 到 index (初始0) 隨機(jī)值 rand, shuffled[index] = shuffled[rand], shuffled[rand] = arr[index]
3.index++ ; 重復(fù)第二步，直到 index = length -1
簡(jiǎn)單來(lái)說(shuō)，就是 shuffled 從 0 到 length-1 的賦值過(guò)程，并且新加入的值是 arr[index]。

代碼實(shí)現(xiàn) 1.代碼一

function random(min, max) {
    if (max == null) {
        max = min;
        min = 0;
    }
    return min + Math.floor(Math.random() * (max - min + 1));
};
function shuffle(arr) {
    var length = arr.length, shuffled = Array(length);
    for (var index = 0, rand; index < length; index++) {
        rand = random(0, index);
        if (rand !== index) shuffled[index] = shuffled[rand];
        shuffled[rand] = arr[index];
    }
    return shuffled;
}

測(cè)試用例：

var arr = ["dfewfew", 2, 3, 4, 5, 6, 7, "fdf"", { kdofkod, jiji, miojim }];
shuffle(arr);

console輸出：

[3, "dfewfew", 7, 2, 4, Array(3), "fdf"", 5, 6]

其中， Array(3)：length:3
0:"kdofkod"
1:"jiji"
2:"miojim"

2.代碼二

function shuffle(arr) {
    var i, j, temp;
    for (i = arr.length - 1; i > 0; i--) {
        j = Math.floor(Math.random() * (i + 1));
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    return arr;
};

測(cè)試用例：

var arr = ["dfewfew", 2, 3, 4, 5, 6, 7, "fdf"", { kdofkod, jiji, miojim }];
shuffle(arr);

console輸出：

[7, 3, "dfewfew", "fdf"", Array(3), 4, 6, 2, 5]

其中， Array(3)：length:3
0:"kdofkod"
1:"jiji"
2:"miojim"

參考資料

Fisher–Yates shuffle 洗牌算法
JavaScript學(xué)習(xí)筆記：數(shù)組隨機(jī)排序
洗牌算法：給數(shù)組隨機(jī)排序
洗牌算法Fisher_Yates原理

GPU云服務(wù)器云服務(wù)器數(shù)組隨機(jī)排序 php數(shù)組隨機(jī)排序字符串排序數(shù)組排序算法隨機(jī)洗牌

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/82264.html

相關(guān)文章

也談前端面試常見問(wèn)題之『數(shù)組亂序』

摘要：看完部分的源碼，首先迫不及待想跟大家分享的正是本文主題數(shù)組亂序。這是一道經(jīng)典的前端面試題，給你一個(gè)數(shù)組，將其打亂，返回新的數(shù)組，即為數(shù)組亂序，也稱為洗牌問(wèn)題。關(guān)于數(shù)組亂序，正確的解法應(yīng)該是，復(fù)雜度。前言終于可以開始 Collection Functions 部分了。可能有的童鞋是第一次看樓主的系列文章，這里再做下簡(jiǎn)單的介紹。樓主在閱讀 underscore.js 源碼的時(shí)候，學(xué)到...

tracy 2019-08-19 18:42 評(píng)論0 收藏0
Underscore 源碼（三）隨機(jī)洗牌算法

摘要：隨機(jī)洗牌算法說(shuō)實(shí)話，以前理解數(shù)組的排序，都是將數(shù)組按照一定的邏輯由大到小或者由小到大排序，我自己是沒(méi)有碰到過(guò)隨機(jī)打亂數(shù)組排序的問(wèn)題。然后里用的是所謂的洗牌算法，很高效。總結(jié)又是三個(gè)知識(shí)點(diǎn)，分別是隨機(jī)洗牌分組和函數(shù)的實(shí)現(xiàn)，沒(méi)什么復(fù)雜的。這是第三篇關(guān)于 Underscore 的源碼解讀，最近一段時(shí)間學(xué)的東西很少，自己太忙了，一方面忙著找實(shí)習(xí)，晚上回去還要寫畢業(yè)論文。畢業(yè)論文真的很憂傷，因...

silencezwm 2019-08-20 16:42 評(píng)論0 收藏0
洗牌算法

摘要：描述拷貝數(shù)組從掃描數(shù)組，選擇一個(gè)隨機(jī)數(shù)新數(shù)組的新數(shù)組的新數(shù)組的原始數(shù)組重復(fù)第步，直到末尾最終的新數(shù)組就是隨機(jī)的參考三種洗牌算法洗牌算法 Fisher-Yates Shuffle Fisher–Yates 隨機(jī)置亂算法，通俗說(shuō)就是生成一個(gè)有限集合的隨機(jī)排列。描述：寫下從 1 到 N 的數(shù)字取一個(gè)從 1 到剩下的數(shù)字（包括這個(gè)數(shù)字）的隨機(jī)數(shù) k 從低位開始，得到第 k 個(gè)還沒(méi)有被...

omgdog 2019-08-23 17:53 評(píng)論0 收藏0
JavaScript30秒，從入門到放棄之Array（五）

摘要：原文地址秒，從入門到放棄之五博客地址秒，從入門到放棄之五水平有限，歡迎批評(píng)指正從給定的數(shù)組中隨機(jī)選出指定個(gè)數(shù)的數(shù)組元素。否則判斷數(shù)組元素是否大于或者等于指定元素，尋找過(guò)程與前邊類似。原文地址：JavaScript30秒，從入門到放棄之Array（五）博客地址：JavaScript30秒，從入門到放棄之Array（五）水平有限，歡迎批評(píng)指正 sampleSize Gets n...

dunizb 2019-08-26 11:41 評(píng)論0 收藏0
JavaScript專題之亂序

摘要：源碼地址為了簡(jiǎn)化篇幅，我們對(duì)這個(gè)數(shù)組進(jìn)行分析，數(shù)組長(zhǎng)度為，此時(shí)采用的是插入排序。插入排序的源碼是其原理在于將第一個(gè)元素視為有序序列，遍歷數(shù)組，將之后的元素依次插入這個(gè)構(gòu)建的有序序列中。 JavaScript 專題系列第十九篇，講解數(shù)組亂序，重點(diǎn)探究 Math.random() 為什么不能真正的亂序？亂序亂序的意思就是將數(shù)組打亂。嗯，沒(méi)有了，直接看代碼吧。 Math.random ...

I_Am 2019-08-21 17:00 評(píng)論0 收藏0