首頁 > web前端 > js教程 > JavaScript學習筆記之數組隨機排序_javascript技巧

JavaScript學習筆記之數組隨機排序_javascript技巧

WBOY
發布: 2016-05-16 15:08:32
原創
1489 人瀏覽過

推薦閱讀:JavaScript學習筆記之數組求和方法

JavaScript學習筆記之數組的增、刪、改、查

JavaScript中提供了sort()和reverse()方法對數組項重新排序。但很多時候這兩個方法無法滿足我們實際業務的需求,比如說撲克牌遊戲中的隨機洗牌。

在這篇文章一起來學習如何完成上面這個範例的效果,以及一些有關於陣列隨機排序的相關知識。

在網路上查了一下有關於陣列隨機排序的相關資料,都看到了Math.random()的身影。開啟瀏覽器控制器,輸入:

Math.random()

從圖中可以看出Math.random()得到的是0~1之間的隨機數。眾所周知,sort()可以呼叫一個函數做為參數,如果這個函數傳回的值為-1表示數組中的a項排在b項前。如此一來,可以寫一個隨機函數,讓Math.random()隨機出來的數與0.5做為一個比較,如果大於.5就返回-1(a排在b前面),反之返回1(b排在a前面):

function randomSort(a, b) {
return Math.random() > 0.5 ? -1 : 1;
}
登入後複製

看範例:

var arr = [1,2,3,4,5,6,7,8,9];
arr.sort(randomSort);
登入後複製

這樣一來,就可以實現文章開頭的範例效果:

雖然前面的方法實現了數組的隨機排序,但總感覺每個元素被派到新數組的位置不是隨機的。就如前面的範例,數組arr中值為1的元素,它的原先鍵值為0,隨機排序後,1的鍵值要求上為0-8的幾率是一樣的。然後這裡是遞減的,原因是sort()方法是依序比較的。

針對這種現象,我們可以用下面這種遞歸的方法來處理:

function randomSort(arr, newArr) {
// 如果原数组arr的length值等于1时,原数组只有一个值,其键值为0
// 同时将这个值push到新数组newArr中
if(arr.length == 1) {
newArr.push(arr[0]);
return newArr; // 相当于递归退出
}
// 在原数组length基础上取出一个随机数
var random = Math.ceil(Math.random() * arr.length) - 1;
// 将原数组中的随机一个值push到新数组newArr中
newArr.push(arr[random]);
// 对应删除原数组arr的对应数组项
arr.splice(random,1);
return randomSort(arr, newArr);
}
登入後複製

如此一來,我們就可以這樣使用:

for (var i = 0; i < 10; i++) {
var arr=[1,2,3,4,5,6,7,8,9];
var newArr=[];
randomSort(arr,newArr);
console.log(newArr);
}
登入後複製

輸出結果:

執行randomSort(arr,newArr)函式之後,原數組arr就清空了。

如果使用這種方法來做文章開頭洗牌的範例,就要在resetPic()函數中重置pukePic數組:

除了上面的兩種方法之外,@Traveller在DIV.IO分享了一篇《數組元素隨機化排序演算法實作》,這篇文章提供了三種數組項隨機排序的實作方法:

使用陣列sort方法對陣列元素隨機排序

Array.prototype.shuffle = function(n) {
var len = this.length ,
num = n &#63; Math.min(n,len) : len,
arr = this.slice(0);
arr.sort(function(a,b){
return Math.random()-0.5;
});
return arr.slice(0,num-1);
}
登入後複製

隨機交換數組內的元素

lib = {}
lib.range = function(min,max) {
return min + Math.floor(Math.random()*(max-min+1));
}

Array.prototype.shuffle = function(n) {
var len = this.length,
num = n &#63; Math.min(n,len) : len,
arr = this.slice(0),
temp,
index;
for (var i=0;i<len;i++){
index = lib.range(i,len-1);
temp = arr[i];
arr[i] = arr[index];
arr[index]=temp;
}
return arr.slice(0,num);
}
登入後複製

隨機從原數組抽取一個元素,加入到新數組

lib = {}
lib.range = function(min,max) {
return min+Math.floor(Math.random()*(max-min+1));
}
Array.prototype.shuffle = function(n) {
var len = this.length, 
num = n &#63; Math.min(n,len) : len,
arr = this.slice(0),
result=[],
index;
for (var i=0;i<num;i++){
index = lib.range(0,len-1-i);
// 或者 result.concat(arr.splice(index,1))
result.push(arr.splice(index,1)[0]);
}
return result
}
登入後複製

洗牌演算法

陣列隨機排序其基本原理是洗牌演算法(Fisher–Yates shuffle):

是一種將有限集合的順序打亂的一種演算法

原理

定義一個陣列(shuffled),長度(length)是原始數組(arr)長度
取 0 到 index (初始0) 隨機值 rand, shuffled[index] = shuffled[rand], shuffled[rand] = arr[index]
index++ ; 重複第二步,直到 index = length -1
是shuffled 從0 到length-1 的賦值過程,並且新加入的值是arr[index],shuffled[index] 的值是已賦值的元素中隨機值shuffled[rand],因為這樣會有兩個重複的值,所以shuffled[rand] 就等於新加入的值arr[index]

underscore.js 中的 shuffle 方法

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 = [1,2,3,4,5,6,7,8,9];
for (var i = 0; i < 10; i++){
console.log(shuffle(arr));
}
登入後複製

Chrome輸出的結果如下:

同樣的,使用洗牌演算法來完成文章最開頭的範例:

還有更簡單易理解的寫法:

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;
};
登入後複製

總結

這篇文章主要總結和收集了有關數組隨機排序我相關資料。當然在坊間實現類似功能的方法還有很多種,這裡只是收集和整理了這些,如果你有更好的方法,歡迎在評論中與我們一起分享。

以上內容是小編給大家介紹的JavaScript學習筆記之數組隨機排序的相關介紹,希望對大家有幫助!

來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板