使用 JavaScript Array.sort() 方法进行洗牌是否正确？

Question

我正在帮助某人解决他的 JavaScript 代码，我的眼睛被一个看起来像这样的部分吸引了：

function randOrd(){
  return (Math.round(Math.random())-0.5);
}
coords.sort(randOrd);
alert(coords);

我的第一个想法是：嘿，这不可能工作！但后来我做了一些实验，发现它确实至少看起来提供了很好的随机结果。

然后我做了一些网络搜索，几乎在顶部找到了一篇文章，其中包含此代码最彻底地复制。 看起来像一个非常受人尊敬的网站和作者......

但我的直觉告诉我，这一定是错误的。 特别是 ECMA 标准没有指定排序算法。 我认为不同的排序算法会导致不同的非均匀洗牌。 有些排序算法甚至可能无限循环......

但你觉得呢？

另一个问题是……我现在该如何测量这种洗牌技术结果的随机性？

更新：我做了一些测量，并将下面的结果发布为答案之一。

Answer 1

在乔恩已经涵盖理论，这是一个实现：

function shuffle(array) {
    var tmp, current, top = array.length;

    if(top) while(--top) {
        current = Math.floor(Math.random() * (top + 1));
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
    }

    return array;
}

算法是O(n)，而排序应该是O(n log n)。 根据与原生 sort() 函数相比执行 JS 代码的开销，这可能会导致 性能存在显着差异，并且随着数组大小的增加而增加。

---

在对 bobobobo 的答案的评论中，我说过所讨论的算法可能不会产生均匀分布的概率（取决于 sort() 的实现）。

我的论点是这样的：排序算法需要一定数量的c比较，例如冒泡排序的c = n(n-1)/2。 我们的随机比较函数使每次比较的结果具有相同的可能性，即存在2^c同样可能的结果。 现在，每个结果必须对应于数组条目的 n! 排列之一，这使得在一般情况下不可能均匀分布。 （这是一种简化，因为所需的实际比较次数取决于输入数组，但断言应该仍然成立。）

正如 Jon 指出的那样，仅凭这一点并没有理由选择 Fisher-Yates 而不是使用 sort() ，因为随机数生成器还将有限数量的伪随机值映射到 n! 排列。 但 Fisher-Yates 的结果应该仍然更好：

Math.random() 生成 [0;1[] 范围内的伪随机数。 由于 JS 使用双精度浮点值，这对应于 2^x 可能的值，其中 52 ≤ x ≤ 63 （我懒得找到实际数字） 。 如果原子事件的数量具有相同的数量级，则使用 Math.random() 生成的概率分布将不再表现良好。

使用 Fisher-Yates 时，相关参数是数组的大小，由于实际限制，数组的大小永远不应接近 2^52。

当使用随机比较函数排序时，该函数基本上只关心返回值是正数还是负数，所以这永远不会成为问题。 但还有一个类似的情况：由于比较函数表现良好，因此如上所述，2^c 可能的结果是同等可能的。 如果 c ~ n log n then 2^c ~ n^(a·n) where a = const，这至少是可能的2^c 与 n! 的量级相同（甚至小于），因此导致分布不均匀，即使排序算法映射到排列上也是如此均匀。 这是否有任何实际影响超出了我的范围。

真正的问题是排序算法不能保证均匀地映射到排列上。 很容易看出合并排序是对称的，但对冒泡排序，或更重要的是快速排序或堆排序之类的推理却不是。

---

底线：只要 sort() 使用合并排序，除了极端情况外，您应该相当安全（至少我希望 2^c ≤ n! 是一种极端情况），如果不是，则一切皆废。

Answer 2

这从来都不是我最喜欢的洗牌方式，部分原因是正如您所说，它是特定于实现的。 特别是，我似乎记得从 Java 或 .NET（不确定是哪一个）排序的标准库通常可以检测到某些元素之间的比较是否不一致（例如，您首先声明 A < B< /code> 和 B ，然后是 C ）。

它最终也会成为比您真正需要的更复杂的洗牌（就执行时间而言）。

我更喜欢洗牌算法，它有效地将集合划分为“洗牌”（在集合开始时，最初为空）和“未洗牌”（集合的其余部分）。 在算法的每个步骤中，选择一个随机的未洗牌元素（可能是第一个）并将其与第一个未洗牌元素交换 - 然后将其视为已洗牌（即在心里移动分区以包含它）。

这是 O(n)，只需要 n-1 次调用随机数生成器，这很好。 它还会产生真正的洗牌 - 任何元素都有 1/n 的机会出现在每个空间中，无论其原始位置如何（假设合理的 RNG）。 排序后的版本近似均匀分布（假设随机数生成器不会两次选择相同的值，如果它返回随机双精度数，则这种情况极不可能），但我发现更容易推理随机播放版本:)

这种方法称为 Fisher-Yates 随机播放。

我认为最好的做法是编写一次洗牌代码，然后在需要洗牌项目的任何地方重复使用它。 那么您无需担心排序实现的可靠性或复杂性。 这只是几行代码（我不会在 JavaScript 中尝试！）

维基百科文章shuffle（尤其是 shuffle 算法部分）讨论了对随机投影进行排序 - 一般而言，值得阅读有关 shuffle 的不良实现的部分，这样您就知道应该避免什么。

Answer 3

我对这种随机排序的结果的随机性做了一些测量...

我的技术是采用一个小数组 [1,2,3,4] 并创建它的所有 (4!= 24) 排列。 然后，我将多次对数组应用改组函数，并计算每个排列生成的次数。 一个好的洗牌算法会将结果相当均匀地分布在所有排列中，而一个坏的洗牌算法不会产生统一的结果。

使用下面的代码我在 Firefox、Opera、Chrome、IE6/7/8 中进行了测试。

令我惊讶的是，随机排序和真正的洗牌都创建了同样均匀的分布。 因此，似乎（正如许多人所建议的那样）主要浏览器正在使用合并排序。 这当然并不意味着不可能有浏览器有不同的做法，但我想说这意味着这种随机排序方法足够可靠，可以在实践中使用。

<强>编辑：这个测试并没有真正正确地测量随机性或缺乏随机性。 请参阅我发布的另一个答案。

但在性能方面，Cristoph 给出的 shuffle 函数显然是赢家。即使对于小型四元素数组，真正的 shuffle 的执行速度也大约是随机排序的两倍！

// The shuffle function posted by Cristoph.
var shuffle = function(array) {
    var tmp, current, top = array.length;

    if(top) while(--top) {
        current = Math.floor(Math.random() * (top + 1));
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
    }

    return array;
};

// the random sort function
var rnd = function() {
  return Math.round(Math.random())-0.5;
};
var randSort = function(A) {
  return A.sort(rnd);
};

var permutations = function(A) {
  if (A.length == 1) {
    return [A];
  }
  else {
    var perms = [];
    for (var i=0; i<A.length; i++) {
      var x = A.slice(i, i+1);
      var xs = A.slice(0, i).concat(A.slice(i+1));
      var subperms = permutations(xs);
      for (var j=0; j<subperms.length; j++) {
        perms.push(x.concat(subperms[j]));
      }
    }
    return perms;
  }
};

var test = function(A, iterations, func) {
  // init permutations
  var stats = {};
  var perms = permutations(A);
  for (var i in perms){
    stats[""+perms[i]] = 0;
  }

  // shuffle many times and gather stats
  var start=new Date();
  for (var i=0; i<iterations; i++) {
    var shuffled = func(A);
    stats[""+shuffled]++;
  }
  var end=new Date();

  // format result
  var arr=[];
  for (var i in stats) {
    arr.push(i+" "+stats[i]);
  }
  return arr.join("\n")+"\n\nTime taken: " + ((end - start)/1000) + " seconds.";
};

alert("random sort: " + test([1,2,3,4], 100000, randSort));
alert("shuffle: " + test([1,2,3,4], 100000, shuffle));

Answer 4

有趣的是，微软在他们的选择随机浏览器页面中使用了相同的技术。

他们使用了略有不同的比较函数：

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

对我来说看起来几乎相同，但是 结果并不是那么随机...

因此，我使用链接文章中使用的相同方法再次进行了一些测试运行，事实上 - 事实证明随机 -排序方法产生了有缺陷的结果。 新的测试代码在这里：

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

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

function shuffle3(array) {
  var tmp, current, top = array.length;

  if(top) while(--top) {
    current = Math.floor(Math.random() * (top + 1));
    tmp = array[current];
    array[current] = array[top];
    array[top] = tmp;
  }

  return array;
}

var counts = [
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0]
];

var arr;
for (var i=0; i<100000; i++) {
  arr = [0,1,2,3,4];
  shuffle3(arr);
  arr.forEach(function(x, i){ counts[x][i]++;});
}

alert(counts.map(function(a){return a.join(", ");}).join("\n"));

Answer 5

我在我的网站上放置了一个简单的测试页面，显示您当前的浏览器与其他流行浏览器的偏差使用不同的方法进行洗牌。 它显示了仅使用 Math.random()-0.5（另一种没有偏见的“随机”洗牌）以及上面提到的 Fisher-Yates 方法的可怕偏见。

您可以看到，在某些浏览器上，某些元素在“随机播放”期间根本不会改变位置的可能性高达 50%！

注意：您可以通过将代码更改为：

function shuffle(array) {
  for (var tmp, cur, top=array.length; top--;){
    cur = (Math.random() * (top + 1)) << 0;
    tmp = array[cur]; array[cur] = array[top]; array[top] = tmp;
  }
  return array;
}

测试结果： http://jsperf.com/optimized-fisher-yates

Answer 6

我认为对于您对分发不挑剔并且希望源代码较小的情况来说，这很好。

在 JavaScript 中（不断传输源代码），小的影响会导致带宽成本的差异。

Answer 7

不，这是不正确的。 正如其他答案所指出的，这将导致不均匀的随机播放，并且随机播放的质量还将取决于浏览器使用的排序算法。

现在，这对您来说可能听起来不太糟糕，因为即使理论上分布不均匀，但实际上它可能几乎均匀，对吗？ 嗯，不，甚至还差得远。 下图分别显示了 Chrome 和 Firefox 中每个元素被打乱到的索引的热图：如果像素 (i, j) 为绿色，则表示索引 i 处的元素经常被洗牌到索引 j，如果它是红色的，那么它在那里洗牌的次数太少了。

这些屏幕截图取自 Mike Bostock 关于此主题的页面。

正如您所看到的，使用随机比较器进行洗牌在 Chrome 中存在严重偏差，在 Firefox 中更是如此。 特别是，两者都沿着对角线有很多绿色，这意味着太多的元素被“洗牌”到非常接近它们在原始序列中的位置的地方。 相比之下，无偏洗牌的类似图表（例如使用 Fisher-Yates 算法）将全部是浅黄色，只有少量随机噪声。

Answer 8

四年过去了，但我想指出的是，无论你使用什么排序算法，随机比较器方法都不会正确分布。

证明：

1. 对于n个元素的数组，恰好有n!个排列（即可能的随机排列）。
2. 洗牌期间的每次比较都是两组排列之间的选择。 对于随机比较器，有 1/2 的机会选择每组。
3. 因此，对于每个排列 p，以排列 p 结束的机会是分母为 2^k 的分数（对于某些 k），因为它是这些分数的总和（例如 1/8 + 1/16 = 3/16 ）。
4. 对于 n = 3，有六种等概率排列。 那么，每次排列的机会是 1/6。 1/6 不能表示为以 2 的幂为分母的分数。
5. 因此，抛硬币排序永远不会导致洗牌的公平分配。

唯一可能正确分布的大小是 n=0,1,2。

---

作为练习，尝试绘制 n=3 时不同排序算法的决策树。

---

证明中存在一个差距：如果排序算法依赖于比较器的一致性，并且在不一致的比较器下具有无限的运行时间，则它可以具有无限的概率之和，即使这样，也允许加起来为 1/6总和中的每个分母都是 2 的幂。尝试找出一个。

此外，如果比较器有固定的机会给出任一答案（例如，对于常数 P，(Math.random() < P)*2 - 1），则上述证明成立。 如果比较器根据之前的答案改变其赔率，则可能会产生公平的结果。 为给定的排序算法找到这样的比较器可能是一篇研究论文。

Answer 9

这当然是一种黑客行为。 实际上，无限循环算法是不可能的。
如果你正在对对象进行排序，你可以循环遍历 coords 数组并执行类似的操作：（

for (var i = 0; i < coords.length; i++)
    coords[i].sortValue = Math.random();

coords.sort(useSortValue)

function useSortValue(a, b)
{
  return a.sortValue - b.sortValue;
}

然后再次循环遍历它们以删除 sortValue）

不过仍然是一个 hack。 如果你想做得好，你就必须用困难的方式来做:)

Answer 10

如果您使用 D3，则有一个内置的随机播放功能（使用 Fisher-Yates）：

var days = ['Lundi','Mardi','Mercredi','Jeudi','Vendredi','Samedi','Dimanche'];
d3.shuffle(days);

Mike 对此进行了详细介绍：

Answer 11

这是使用单个数组的方法：

基本逻辑是：

从包含 n 个元素的数组开始

从数组中删除一个随机元素并将其推送到数组中

从数组的前 n - 1 个元素中删除一个随机元素并将其推送到数组中

从前 n - 2 个元素中删除一个随机元素数组的元素并将其推入数组

...

删除数组的第一个元素并将其推入数组

代码：

for(i=a.length;i--;) a.push(a.splice(Math.floor(Math.random() * (i + 1)),1)[0]);

Answer 12

您可以使用 Array.sort () 函数来打乱数组 - 是。

结果是否足够随机 - 否。

考虑以下代码片段：

/*
 * The following code sample shuffles an array using Math.random() trick
 * After shuffling, the new position of each item is recorded
 * The process is repeated 100 times
 * The result is printed out, listing each item and the number of times
 * it appeared on a given position after shuffling
 */
var array = ["a", "b", "c", "d", "e"];
var stats = {};
array.forEach(function(v) {
  stats[v] = Array(array.length).fill(0);
});
var i, clone;
for (i = 0; i < 100; i++) {
  clone = array.slice();
  clone.sort(function() {
    return Math.random() - 0.5;
  });
  clone.forEach(function(v, i) {
    stats[v][i]++;
  });
}
Object.keys(stats).forEach(function(v, i) {
  console.log(v + ": [" + stats[v].join(", ") + "]");
});

示例输出：

a: [29, 38, 20,  6,  7]
b: [29, 33, 22, 11,  5]
c: [17, 14, 32, 17, 20]
d: [16,  9, 17, 35, 23]
e: [ 9,  6,  9, 31, 45]

理想情况下，计数应均匀分布（对于上面的示例，所有计数应约为 20）。 但他们不是。 显然，分布取决于浏览器实现的排序算法以及它如何迭代数组项进行排序。

Answer 13

没有什么问题。

您传递给 .sort() 的函数通常看起来像

function sortingFunc( first, second )
{
  // example:
  return first - second ;
}

您在 sortingFunc 中的工作是返回：

• 如果第一个在第二个之前，则返回负数
• 如果第一个应该在第二个之后，则返回正数 如果
• 它们在第二个之后，则返回 0完全相等

上面的排序函数将事物按顺序排列。

如果您随机返回 - 和 + ，您将得到随机排序。

就像在 MySQL 中一样：

SELECT * from table ORDER BY rand()