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

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

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

原理及步驟

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

代碼實現(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;
}

測試用例：

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;
};

測試用例：

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ù)組隨機排序
洗牌算法：給數(shù)組隨機排序
洗牌算法Fisher_Yates原理

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

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

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

相關(guān)文章

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

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

tracy 2019-08-19 18:42 評論0 收藏0
Underscore 源碼（三）隨機洗牌算法

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

silencezwm 2019-08-20 16:42 評論0 收藏0
洗牌算法

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

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

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

dunizb 2019-08-26 11:41 評論0 收藏0
JavaScript專題之亂序

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

I_Am 2019-08-21 17:00 評論0 收藏0