DIV CSS 佈局教程網

用 sort 洗牌?陣列隨機排序的做法與它的陷阱
編輯:關於JavaScript     

需要把陣列元素打亂順序時,網路上流傳最廣的寫法是拿 sort 配上一個隨機比較函數。它確實能跑,但並不是好方案。

var list = [1, 2, 3, 4, 5, 6, 7, 8, 9];
list = list.sort(function() { return Math.random() - 0.5; });
Print(list);   // 例如:4,3,1,2,9,5,6,7,8

為什麼這樣不可靠

排序演算法的前提是「比較結果必須一致」——同一對元素比較兩次應該得到相同答案。而 Math.random() - 0.5 每次都回傳不同的值,等於給排序演算法餵入自相矛盾的資訊。後果是打亂的程度並不均勻:某些排列出現的機率會明顯高於其他,而且不同瀏覽器引擎的排序實作不同,結果也不一致。

正確做法:Fisher–Yates 洗牌演算法

從尾端往前掃,每一輪在「剩餘範圍」內隨機挑一個位置與當前位置交換:

function shuffle(arr) {
  for (var i = arr.length - 1; i > 0; i--) {
    var j = Math.floor(Math.random() * (i + 1));
    var tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }
  return arr;
}

var list = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(shuffle(list));

這個演算法能保證 n 個元素的每一種排列出現機率完全相同,時間複雜度 O(n),也只跟原陣列交換,不需要額外的比較邏輯。打牌、抽獎、隨機抽樣題組等情境都應該用它,而不是 sort。

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