DIV CSS 佈局教程網

從 sort 洗牌到 Fisher–Yates:JavaScript 陣列隨機打亂的正確做法
編輯:關於JavaScript     

要把 ['a','b','c','d'] 隨機打亂順序,網路上流傳最廣的寫法是這個:

function RandomSort(a, b) {
  return 0.5 - Math.random();
}
// arr.sort(RandomSort);

看起來很聰明,實際上分佈並不均勻。原因是 sort 需要一個「一致的比較結果」才能收斂,而每次呼叫都回傳隨機值,等於給排序演算法一份自相矛盾的輸入,某些排列出現的機率會明顯高於其他。元素一多,偏差還會被放大。

正解:Fisher–Yates(又稱 Knuth)洗牌

它的思路非常樸素:從後往前,每一格都跟「它自己或它前面的某一格」交換。這樣每個元素落到每個位置的概率都恰好是 1/n。

/* jshint -W054 */
(function (exports) {
  'use strict';

  // Fisher–Yates (Knuth) shuffle
  function shuffle(array) {
    var currentIndex = array.length, temporaryValue, randomIndex;

    // 只要還有元素沒處理完
    while (currentIndex !== 0) {
      // 從剩餘的 0 ~ currentIndex-1 中挑一個
      randomIndex = Math.floor(Math.random() * currentIndex);
      currentIndex -= 1;

      // 跟目前這格交換
      temporaryValue = array[currentIndex];
      array[currentIndex] = array[randomIndex];
      array[randomIndex] = temporaryValue;
    }
    return array;
  }

  exports.knuthShuffle = shuffle;
}('undefined' !== typeof exports && exports
  || 'undefined' !== typeof window && window || global));

瀏覽器端用法(注意 shuffle 會直接改動原陣列,想保留原樣要先 slice 一份):

(function () {
  'use strict';
  var a = [2, 11, 37, 42], b;

  // a.slice(0) 產生副本, shuffle 只動副本
  b = window.knuthShuffle(a.slice(0));
  console.log(b);   // 例如 [37, 2, 42, 11]
  console.log(a);   // [2, 11, 37, 42] 不變
}());

Node.js 則透過 npm 安裝:

npm install -S knuth-shuffle

(function () {
  'use strict';
  var shuffle = require('knuth-shuffle').knuthShuffle;
  var a = [2, 11, 37, 42];
  var b = shuffle(a.slice(0));
  console.log(b);
}());

同一個演算法的常見變形

倒數 for 迴圈版(Durstenfeld 寫法,最容易記):

/**
 * 原地隨機重排陣列,使用 Durstenfeld 洗牌演算法
 */
function shuffleArray(array) {
  for (var i = array.length - 1; i > 0; i--) {
    var j = Math.floor(Math.random() * (i + 1));
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
  return array;
}

ES2015 解構賦值版,省掉暫存變數:

Array.prototype.shuffle = function () {
  let m = this.length, i;
  while (m) {
    i = (Math.random() * m--) >>> 0;
    [this[m], this[i]] = [this[i], this[m]];
  }
  return this;
};

[1, 2, 3, 4, 5, 6, 7].shuffle();

不過擴充原型這件事最好避免,它會污染全域、也可能與其他函式庫衝突。改成獨立函式更安全:

function shuffle(arr) {
  const result = arr.slice();
  for (let i = result.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [result[i], result[j]] = [result[j], result[i]];
  }
  return result;   // 不回傳原陣列,改動可控
}

中文搜尋「隨機演算法」會跑出大量 sort 變體,但均勻性、效率與相容性都經不起檢驗。需要打亂陣列時,直接用 Fisher–Yates 就對了;若你的場景是抽樣(例如抽獎、隨機出題),下一則的 getRandomArrayElements 是更省成本的寫法。

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