洗牌Javascript數組優雅

Question

大約有洗牌JS數組一些現有的線程，但他們似乎都沒有瑣碎和不優雅，由多行代碼。

我遇到了一些博客，得到了如下的一條線「解決辦法」：

yourArray.sort(function() { return 0.5 - Math.random() }); 

如果你不熟悉的排序算法是如何工作的，我會解釋這裏簡單介紹一下它的總是關於比較兩個值的數組，然後做出決定。所提出的解決方案使用另一個函數「覆蓋」默認比較函數，該函數對於兩個單元的每次比較產生隨機值（在每次比較時它隨機地決定哪個大於哪個）。

它的問題是，我不知道哪個排序算法是由每個網頁瀏覽器。對於一些排序算法，例如冒泡，這樣的功能可能會導致排序算法永遠運行，因爲這將有二分之一^（長度）概率爲具有不帶任何交換運行。這似乎也是Quicksort有問題。我認爲這將完成定期只有在網絡瀏覽器使用歸併或堆排序

沒有人嘗試一下，可以告訴它是否是安全的或其他的解決方案建議？

Answer 1

「解決方法」是一個可怕的想法。這是效率低下的（使用更多的Math.random()而不是必要的），正如你所說的，對於一些排序算法是很危險的。這也是有偏見的（至少對於我的nodeJS安裝中的sort()版本，儘管我無法解釋爲什麼）。這裏的分選陣列[1, 2, 3] 60000倍和計數多少每個排列的典型結果顯示了：

[1，2，3]：14821倍
[1,3，2]：7637倍
[2,1，3]：15097倍
[2,3，1]：7590倍
[3,1，2]：7416倍
[3,2，1]：7439倍

對於無偏差洗牌，六個排列應該出現eq平均而言常常是6萬次重複的約10000次。在我的實驗中，[1，2，3]和[2，1，3]出現的頻率大約是其他四種排列的兩倍。這在測試的許多次運行中都是一致的。

你好得多粘到標準費雪耶茨洗牌（在網絡上的this Wikipedia article和其他許多地方所描述的）。在僞代碼，它看起來像這樣（從維基百科的文章取）：

-- To shuffle an array a of n elements (indices 0..n-1): 
for i from n−1 downto 1 do 
    j ← random integer such that 0 ≤ j ≤ i 
    exchange a[j] and a[i] 

不要太複雜，絕對是一個更好的辦法。這是我的JavaScript版本（可能會清理一下）：

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

P.S.作爲參考，這裏是我用來測試你的解決方法的代碼：

function shuffleRandomSort(a) { 
    a.sort(function() { return 0.5 - Math.random() }); 
    return a; 
} 

function score(scores, result) { 
    var index; 
    if (result[0] === 1) { 
     index = result[1] === 2 
      ? 0 // [1, 2, 3] 
      : 1; // [1, 3, 2] 
    } else if (result[0] === 2) { 
     index = result[1] === 1 
      ? 2 // [2, 1, 3] 
      : 3; // [2, 3, 1] 
    } else { // result[0] === 3 
     index = result[1] === 1 
      ? 4 // [3, 1, 2] 
      : 5; // [3, 2, 1] 
    } 
    scores[index]++; 
} 

function runTest(shuffler, n) { 
    var scores = [0, 0, 0, 0, 0, 0], 
     a; 
    for (var i = 0; i < n; ++i) { 
     a = [1, 2, 3]; 
     score(scores, shuffler(a)); 
    } 
    console.log(scores); 
} 

console.log(shuffleRandomSort, runTest(60000)); 

Answer 2

我抓住一些算法，並與console.time測試了它們，你可以看到結果運行它們：

var smallArray = Array.from({ length: 10 }, (x, i) => i); 
 
var bigArray = Array.from({ length: 1000 }, (x, i) => i); 
 

 
function shuffle1(array) { 
 
    var currentIndex = array.length, temporaryValue, randomIndex; 
 

 
    while (currentIndex) { 
 
    randomIndex = (Math.random() * currentIndex) | 0; 
 
    currentIndex -= 1; 
 

 
    temporaryValue = array[currentIndex]; 
 
    array[currentIndex] = array[randomIndex]; 
 
    array[randomIndex] = temporaryValue; 
 
    } 
 
} 
 

 
function shuffle2(arr) { 
 
    return _.shuffle(arr); 
 
} 
 

 
function shuffle3(arr) { 
 
    for (let i = arr.length - 1; i >= 0; --i) { 
 
    let j = (Math.random() * i) | 0; 
 
    [arr[i], arr[j]] = [arr[j], arr[i]]; 
 
    } 
 
} 
 

 
// inconsistent speeds 
 
function shuffle4(arr) { 
 
    arr.sort(function() { return 0.5 - Math.random() }); 
 
} 
 

 
function test(label, fn) { 
 
    console.time(label); 
 
    for (let i = 0; i < 1000; ++i) { 
 
    fn(); 
 
    } 
 
    console.timeEnd(label); 
 
} 
 

 
// time in comments based on Chrome 55 
 

 
let sa1 = smallArray.slice(0); 
 
let sa2 = smallArray.slice(0); 
 
let sa3 = smallArray.slice(0); 
 
let sa4 = smallArray.slice(0); 
 
test('smallArray shuffle1',() => shuffle1(sa1)); // 0.785ms 
 
test('smallArray shuffle2',() => shuffle2(sa2)); // 1.830ms 
 
test('smallArray shuffle3',() => shuffle3(sa3)); // 5.540ms 
 
test('smallArray shuffle4',() => shuffle4(sa4)); // 3.995ms 
 

 
let ba1 = bigArray.slice(0); 
 
let ba2 = bigArray.slice(0); 
 
let ba3 = bigArray.slice(0); 
 
let ba4 = bigArray.slice(0); 
 
test('bigArray shuffle1',() => shuffle1(ba1)); // 14.195ms 
 
test('bigArray shuffle2',() => shuffle2(ba2)); // 24.645ms 
 
test('bigArray shuffle3',() => shuffle3(ba3)); // 119.425ms 
 
test('bigArray shuffle4',() => shuffle4(ba4)); // 249.930ms

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js"></script>