JavaScript 入門指南 - 洗牌演算法

洗牌演算法 (algorithm) 的名稱來自於撲克牌遊戲，把一副 52 張撲克牌攪亂順序就是洗牌

我們採用的演算法如下順序

取得陣列長度 i

取得 0 到 i - 1 的隨機索引值 j

將該索引值的元素 a[j] 暫存起來

將 a[i] 與 a[j] 交換

i 遞減

重複 2 直到 i 為 0 為止

例如施用在下面陣列 (array) a

var a = [1, 2, 3, 4, 5, 6, 7, 8, 9];

首先取得陣列長度 i

var i = a.length;

然後利用迴圈 (loop) 進行 2 到 6 的工作

while (i) {
    var j = parseInt(Math.random() * i);
    var k = a[--i];
    a[i] = a[j];
    a[j] = k;
}

Math 為內建物件 (object) 之一，回傳 0 到 1 之間的隨機浮點數，將之乘上 i ，就會得到 0 到 i 之間的隨機數，不過這數字是浮點數，因此用內建函數 parseInt() 取得整數 j ，這就是我們需要的 0 到 i - 1 之間的隨機索引值。

例如第一次取得 j 的值為 5

var j = parseInt(Math.random() * i);

下面就會先將 a[8] 的值儲存到變數 k ，這裡在中括弧內用遞減運算子，目的是取得最後一個元素值

var k = a[--i];

然後把 a[5] 的內容搬到 a[8]

a[i] = a[j];

最後把 k 的內容，也就是原先 a[8] 的值搬移到 a[5]

a[j] = k;

迴圈會一直將 i 遞減到 0 為止，也就是從最後一個陣列元素開始，隨機與之前的元素交換，然後逐次到第一個元素，藉此攪亂整個陣列的順序。

換成字母表陣列，我們寫成完整例子如下

<html>
<head>
<title>Shuffle Demo</title>
<script>
function run() {
    var d = document.getElementById("display");    
    var a = "abcdefghijklmnopqrstuvwxyz".split("", 26);
    var i = a.length;
    while (i) {
        var j = parseInt(Math.random() * i);
        var k = a[--i];
        a[i] = a[j];
        a[j] = k;
    }
    
    d.innerHTML += a;
}
</script>
</head>
<body onload="run()">
<div id="display"></div>
</body>
</html>

<!-- 《程式語言教學誌》的範例程式
      http://pydoing.blogspot.com/
      檔名：shffledemo.html
      功能：示範 JavaScript 程式
      作者：張凱慶
      時間：西元 2012 年 12 月 -->

瀏覽器開啟如下

結果還不錯，這就是我們要的密碼表了。下面我們要開始進入開發編密碼用的 Encrypt 物件了，先來看看網頁 Encode Software 概觀吧！

中英文術語對照
陣列	array
物件	object
資料型態	data type
建構子	constructor
迴圈	loop
方法	method
字串	string
參數	parameter
演算法	algorithm

您可以繼續參考

網頁軟體開發

認識 HTML DOM

陣列

洗牌演算法

Encode Software 概觀

資料驗證

自訂 Encrypt 物件

控制函數與整合 Encrypt 物件

完成版的 Encode Software

下一步

相關目錄

回 JavaScript 入門指南
回 JavaScript 教材
回首頁

參考資料

https://developer.mozilla.org/en-US/docs/JavaScript/Guide/Predefined_Core_Objects
http://www.w3schools.com/JS/js_obj_array.asp
http://www.tutorialspoint.com/javascript/javascript_arrays_object.htm

Search This Blog

Nintendo E3