洗牌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>