DIV CSS 佈局教程網

JavaScript 學習筆記:陣列隨機排序(洗牌)的各種實作
編輯:關於JavaScript     

JavaScript 提供了 sort() 與 reverse() 來重排陣列,但很多時候這兩個方法並不能滿足需求,最典型的就是撲克牌遊戲裡的隨機洗牌。

這篇文章就來整理陣列隨機排序的幾種做法,以及背後的原理。

先從 Math.random() 開始

查資料時到處都看得到 Math.random() 的身影。打開瀏覽器主控台輸入:

它回傳的是 0 到 1 之間的隨機數。既然 sort() 可以接受一個比較函式,回傳 -1 代表 a 排在 b 前面,那麼寫一個隨機比較函式就行了:

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

如此一來,文章開頭的效果就做完了。

但仔細想會發現問題:每個元素被分到新位置的機率其實不是均勻的。以值為 1 的元素為例,原本索引是 0,隨機排序後它落在 0 到 8 任一位置的機率理論上應該相同,實際上卻呈現遞減——因為 sort() 是依序比較的,比較的結果會互相牽連。

遞迴抽樣法

針對這個問題,可以改用「隨機抽一個、剩下的再抽」的遞迴做法:

 function randomSort(arr, newArr) {
   // 原陣列只剩一個值時,直接推進新陣列並結束遞迴
   if(arr.length == 1) {
     newArr.push(arr[0]);
     return newArr;
   }
   // 在長度範圍內取一個隨機索引
   var random = Math.ceil(Math.random() * arr.length) - 1;
   // 把隨機抽到的值推進新陣列
   newArr.push(arr[random]);
   // 從原陣列移除該項
   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 會被清空。所以若要用它來做開頭的洗牌範例,記得在 reset 函式裡把牌堆重新還原。

另外三種思路

社群裡也整理過幾種做法,共同點是先用 slice(0) 複製一份,避免動到原陣列。

一、用 sort 隨機排序

 Array.prototype.shuffle = function(n) {
   var len = this.length ,
       num = n ? 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 ? 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 ? 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.push(arr.splice(index,1)[0]);
   }
   return result
 }

洗牌算法(Fisher–Yates)

陣列隨機排序背後的基本原理,就是 Fisher–Yates shuffle:一種把有限集合的順序打亂的算法。

原理
定義一個新陣列(shuffled),長度等於原陣列(arr)的長度;取 0 到 index(初始為 0)之間的隨機值 rand,令 shuffled[index] = shuffled[rand]、shuffled[rand] = arr[index];index 遞增後重複,直到 index 等於 length - 1。因為新加入的值是 arr[index],而 shuffled[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;
 };

總結

本文整理了幾種陣列隨機排序的做法。坊間實作還有很多種,這裡只收錄這些;如果你有更好的寫法,歡迎一起交流。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved