JS實(shí)現(xiàn)數(shù)組隨機(jī)排序的三種方法詳解

更新時(shí)間：2022年05月20日 10:23:14 作者：接著奏樂(lè)接著舞。

這篇文章主要為大家詳細(xì)介紹了JavaScript中實(shí)現(xiàn)數(shù)組隨機(jī)排序的三種方式，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)或工作有一定參考價(jià)值，需要的可以參考一下

1.利用數(shù)組方法sort實(shí)現(xiàn)隨機(jī)排序

實(shí)現(xiàn)隨機(jī)排序方法還是很多的，用for循環(huán)是可以寫的，用Lodash等三方j(luò)s方法庫(kù)也行。但個(gè)人以為使用sort比較方便，但是他又缺點(diǎn)，缺點(diǎn)就是不夠那么的隨機(jī)，我看過(guò)sort運(yùn)行機(jī)制后，發(fā)現(xiàn)他竟然是利用一個(gè)比較器兩兩比較出來(lái)的。

var arr = [1, 2, 3, 4, 5]
 
arr.sort(function () {
  return Math.random() - 0.5
})
console.log(arr);

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

從原始數(shù)組中每次隨機(jī)選中一個(gè)元素，然后放入新數(shù)組中，每取出一個(gè)元素后，將將它從原數(shù)組中取出（使用splice方法），原數(shù)組長(zhǎng)度減一。

舉例：

現(xiàn)在我有紅桃K、黑桃A、小王三張牌，要求打亂順序，你可以從三張牌抽出任意一張，假設(shè)你抽到的是小王，那么我手里三張牌變成兩張牌，你手里變成1張牌，以此類推，實(shí)現(xiàn)隨機(jī)排序。

代碼實(shí)現(xiàn)：

function shuffle(array){
    let res = [], random;
    while(array.length>0){
        random = Math.floor(Math.random()*array.length);
        res.push(array[random]);
        array.splice(random, 1);
    }
    return res;
}
 
console.log(shuffle([1,2,3,4,5]));

3.洗牌算法深入分析

思路：我有一副牌，隨機(jī)抽取牌，舊的牌數(shù)量相應(yīng)減少!

function shuffle(m) //洗牌 //抽牌法
{
//生成m張牌
var arr = new Array(m);
for (var i=0; i<m; i++) {
arr[i] = i;
}
//每次抽出一張牌，需要遍歷整個(gè)數(shù)組，所以很耗時(shí)。
var arr2 = new Array();
for (var i=m; i>0; i–) {
var rnd = Math.floor(Math.random()*i);
arr2.push(arr[rnd]);
arr.splice(rnd,1);
}
return arr2;
}

但是這樣的話，因?yàn)閿?shù)組如果很大的話，刪除中間的某個(gè)元素，會(huì)導(dǎo)致后面的數(shù)據(jù)被執(zhí)行，會(huì)對(duì)性能影響很大。

我們刪除那個(gè)元素的目的就是為了不產(chǎn)生空牌。

除了刪除那個(gè)元素之外，我們是不是還有其它方式來(lái)去除空牌？

只需把最后一張未抽的牌放在那個(gè)抽走的位置上就可以了。

順著這個(gè)思路我們可以優(yōu)化成這樣：

代碼如下:

function shuffle_pick(m) //洗牌 //抽牌法優(yōu)化牌
{
//生成m張牌
var arr = new Array(m);
for (var i=0; i<m; i++) {
arr[i] = i;
}
//每次抽出一張牌，放在另一堆。把最后一張未抽的牌放在空位子上。
var arr2 = new Array();
for (var i=m; i>0;) {
var rnd = Math.floor(Math.random()*i);
arr2.push(arr[rnd]);
arr[rnd] = arr[–i];
}
return arr2;
}

除了抽牌思路，我們還可以用換牌思路：

“隨機(jī)交換兩個(gè)位置，共交換n次，n越大，越接近隨機(jī)”。

順著這個(gè)思路，做一點(diǎn)小調(diào)整就可以了：第i張與任意一張牌換位子，換完一輪即可。

代碼如下:

function shuffle_swap(m) //洗牌 //換牌法
{
//生成m張牌
var arr = new Array(m);
for (var i=0; i<m; i++) {
arr[i] = i;
}
//第i張與任意一張牌換位子，換完一輪即可
for (var i=0; i<m; i++) {
var rnd = Math.floor(Math.random()*(i+1)),
temp = arr[rnd];
arr[rnd] = arr[i];
arr[i]=temp;
}
return arr;
}

除了抽牌與換牌的思路，我們還可以用插牌的思路：先有一張牌，第二張牌有兩個(gè)位置可隨機(jī)插入（第一張牌前，或后），第三張牌有三個(gè)位置可隨機(jī)插入（放在后面，或插在第一位，或插在第二位），依此類推

代碼如下:

function shuffle_insert_1(m) //洗牌 //插牌法
{
//每次生成一張最大的牌，插在隨機(jī)的某張牌前。因?yàn)橐跀?shù)組里插入元素，把后面的所有元素向后擠一位，所以很耗時(shí)。
var arr = [0];
for (var i=1; i<m; i++) {
arr.splice(Math.floor(Math.random()*(i+1)),0,i);
}
return arr;
}

以上的代碼也會(huì)有一些問(wèn)題：就是隨著牌數(shù)的增多，插牌變得越來(lái)越困難，因?yàn)椴迮茣?huì)導(dǎo)致后面的很多牌都往后推一步。

當(dāng)然，我們也可以適當(dāng)?shù)膬?yōu)化一下：先有n-1張牌，第n張牌放在最后，然后與任意一張牌互換位置。

代碼如下：

function shuffle_insert(m) //洗牌 //插牌法優(yōu)化版，可以用數(shù)學(xué)歸納法證明，這種洗牌是均勻的。
{
//每次生成一張最大的牌，與隨機(jī)的某張牌換位子
var arr = new Array(m);
arr[0] = 0;
for (var i=1; i<m; i++) {
var rnd = Math.floor(Math.random()*(i+1));
arr[i] = arr[rnd];
arr[rnd] = i;
}
return arr;
}

全部代碼

代碼如下:

<html>
<head>
<meta http-equiv=”Content-Type” content=”text/html; charset=gb2312″>
<title>JK：javascript 洗牌算法 </title>
</head>
<body>
<script type=”text/javascript”>
function shuffle_pick_1(m) //洗牌 //抽牌法
{
//生成m張牌
var arr = new Array(m);
for (var i=0; i<m; i++) {
arr[i] = i;
}
//每次抽出一張牌，放在另一堆。因?yàn)橐跀?shù)組里抽出元素，把后面的所有元素向前拉一位，所以很耗時(shí)。
var arr2 = new Array();
for (var i=m; i>0; i–) {
var rnd = Math.floor(Math.random()*i);
arr2.push(arr[rnd]);
arr.splice(rnd,1);
}
return arr2;
}
function shuffle_pick(m) //洗牌 //抽牌法優(yōu)化牌
{
//生成m張牌
var arr = new Array(m);
for (var i=0; i<m; i++) {
arr[i] = i;
}
//每次抽出一張牌，放在另一堆。把最后一張未抽的牌放在空位子上。
var arr2 = new Array();
for (var i=m; i>0;) {
var rnd = Math.floor(Math.random()*i);
arr2.push(arr[rnd]);
arr[rnd] = arr[–i];
}
return arr2;
}
function shuffle_swap(m) //洗牌 //換牌法
{
//生成m張牌
var arr = new Array(m);
for (var i=0; i<m; i++) {
arr[i] = i;
}
//第i張與任意一張牌換位子，換完一輪即可
for (var i=0; i<m; i++) {
var rnd = Math.floor(Math.random()*(i+1)),
temp = arr[rnd];
arr[rnd] = arr[i];
arr[i]=temp;
}
return arr;
}
function shuffle_insert_1(m) //洗牌 //插牌法
{
//每次生成一張最大的牌，插在隨機(jī)的某張牌前。因?yàn)橐跀?shù)組里插入元素，把后面的所有元素向后擠一位，所以很耗時(shí)。
var arr = [0];
for (var i=1; i<m; i++) {
arr.splice(Math.floor(Math.random()*(i+1)),0,i);
}
return arr;
}
function shuffle_insert(m) //洗牌 //插牌法優(yōu)化版，可以用數(shù)學(xué)歸納法證明，這種洗牌是均勻的。
{
//每次生成一張最大的牌，與隨機(jī)的某張牌換位子
var arr = new Array(m);
arr[0] = 0;
for (var i=1; i<m; i++) {
var rnd = Math.floor(Math.random()*(i+1));
arr[i] = arr[rnd];
arr[rnd] = i;
}
return arr;
}
//alert(shuffle_pick(10))
var funcs = [shuffle_pick_1, shuffle_pick, shuffle_swap, shuffle_insert_1, shuffle_insert],
funcNames = [“抽牌”, “抽牌優(yōu)化”, “換牌”, “插牌”, “插牌優(yōu)化”]
m = 10000,
times=[];
for(var i = 0; i < funcs.length; i++){
var d0= new Date();
funcs[i](m);
funcNames[i] = (new Date() – d0) + ‘\t' + funcNames[i];
}
alert(funcNames.join(‘\n'));
</script>
</body>
</html>

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

您可能感興趣的文章: