在 Jon 已经涵盖了理论之后，这是一个实现：

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()如果原子事件的数量处于相同的数量级，则使用 using 生成的概率分布将不再表现良好。

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

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

真正的问题是排序算法不能保证均匀地映射到排列上。很容易看出 Mergesort 是对称的，但对诸如 Bubblesort 或更重要的 Quicksort 或 Heapsort 之类的东西进行推理则不然。

底线：只要sort()使用 Mergesort，你应该是相当安全的，除非在极端情况下（至少我希望这2^c ≤ n!是一个极端情况），否则，所有的赌注都会被取消。

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

它也最终成为比您真正需要的更复杂的（在执行时间方面）洗牌。

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

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

这种方法称为Fisher-Yates shuffle。

我认为将这种 shuffle 编码一次并在需要 shuffle 项目的任何地方重用它是最佳实践。然后您无需担心排序实现的可靠性或复杂性。只有几行代码（我不会在 JavaScript 中尝试！）

将在洗牌维基百科的文章值得一读的一般洗牌的差实现的部分，所以你知道，以避免什么- （尤其是洗牌的算法部分）有关排序随机投影会谈。

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

我的技术是采用一个小数组 [1,2,3,4] 并创建它的所有 (4! = 24) 排列。然后我会将 shuffling 函数大量应用于数组，并计算每个排列生成的次数。一个好的改组算法会将结果非常均匀地分布在所有排列上，而一个坏的算法不会产生那种统一的结果。

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

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

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

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

// Cristoph 发布的 shuffle 函数。
var shuffle = 函数（数组）{
    var tmp, 当前, 顶部 = array.length;

    if(top) while(--top) {
        当前 = Math.floor(Math.random() * (top + 1));
        tmp = 数组[当前]；
        数组[当前] = 数组[顶部];
        数组[顶部] = tmp;
    }

    返回数组；
};

// 随机排序函数
var rnd = 函数（）{
  返回 Math.round(Math.random())-0.5;
};
var randSort = 函数（A）{
  返回 A.sort(rnd);
};

var排列=函数（A）{
  如果（A.length == 1）{
    返回 [A];
  }
  别的 {
    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]));
      }
    }
    退回烫发；
  }
};

var 测试 = 函数（A，迭代，函数）{
  // 初始化排列
  无功统计= {};
  var perms = permutations(A);
  for (var i in perms){
    统计[""+perms[i]] = 0;
  }

  // 多次洗牌并收集统计信息
  var start=new Date();
  for (var i=0; i<iterations; i++) {
    var shuffled = func(A);
    统计[""+洗牌]++;
  }
  var end=new Date();

  // 格式化结果
  无功 arr=[];
  for (var i in stats) {
    arr.push(i+" "+stats[i]);
  }
  return arr.join("\n")+"\n\n所用时间：" + ((end - start)/1000) + " seconds.";
};

alert("随机排序：" + test([1,2,3,4], 100000, randSort));
警报（“洗牌：”+测试（[1,2,3,4]，100000，洗牌））；

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

他们使用了一个稍微不同的比较函数：

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"));

我在我的网站上放置了一个简单的测试页面，显示您当前浏览器与使用不同方法进行随机播放的其他流行浏览器的偏差。它显示了仅使用 的可怕偏差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