详细说明js数组的完全随机排列算法

Array.prototype.sort方法被许多JavaScript程序员错误地用来随机排列数组。最近在前端明星项目挑战赛项目中，我们发现很多同学用Array.prototype.sort洗牌。

洗牌

以下是常见的完全错误的随机置换算法：

函数shuffle(arr){ return arr . sort(function(){ return math . random()-0.5；});}上面的代码似乎巧妙地使用了Array.prototype.sort来实现随机性，但是存在严重的问题，甚至是完全错误。

证明Array.prototype.sort随机算法的误差

为了证明该算法的误差，我们设计了一种测试方法。假设这个排序算法是正确的，这个算法应用于随机数组[0，1，2，3，4，5，6，7，8，9]。如果算法是正确的，每个数字出现在每个位的概率是相等的。因此，将数组重复洗牌足够多次，然后将每次的结果加到每个位中，最后取每个位的平均值，应该等于(0 9)/2=4.5。测试次数越多，每个比特的平均值应该越接近4.5。因此，我们简单地实现测试代码如下：

var arr=[0，1，2，3，4，5，6，7，8，9]；var res=[0，0，0，0，0，0，0，0，0，0，0]；var t=10000for(var I=0；I t；I){ var sorted=shuffle(arr . slice(0))；sorted.forEach(function(o，I){ RES[I]=o；});}res=res.map(函数(o){ return o/t；});console . log(RES)；用这个测试代码在chrome浏览器中测试上面的shuffle方法，就可以得到结果了。发现结果不是随机分布的，每个位置的平均值都比较大，也就是说随机算法越大，后面出现数字的概率就越高。

为什么会产生这个结果？我们需要确切知道Array.prototype.sort是如何工作的。

首先，我们知道排序算法有很多，但是ECMAScript没有指定Array.prototype.sort必须使用哪种排序算法。

排序不是我们今天要讨论的话题，但无论使用什么排序算法，都需要对两个数字进行比较和交换，排序算法的效率与两个数字比较和交换的次数有关。

最基本的排序是冒泡排序和插入排序。原始冒泡排序和插入排序比较n(n-1)/2次，也就是说任意两个位置的元素比较一次。这种情况下，如果采用之前的排序随机算法，因为每次比较都有50%的交换机会，没有交换，那么结果是随机的还是均匀的？我们可以看看这个例子：

函数bubbleSort(arr，compare){ var len=arr . length；for(var I=0；I len-1；I){ for(var j=0；j len-1-I；j){ var k=j ^ 1；if(compare(arr[j]，arr[k])0){ var tmp=arr[j]；arr[j]=arr[k]；arr[k]=tmp；} } }返回arr}函数shuffle(arr){ return bubbleSort(arr，function(){ return math . random()-0.5；});}var arr=[0，1，2，3，4，5，6，7，8，9]；var res=[0，0，0，0，0，0，0，0，0，0，0]；var t=10000for(var I=0；I t；I){ var sorted=shuffle(arr . slice(0))；sorted.forEach(function(o，I){ RES[I]=o；});}res=res.map(函数(o){ return o/t；});console . log(RES)；以上代码的随机结果也是参差不齐，以后测试平均值的结果更大。(作者之前没有复制原数组，所以错误得出统一结论，2016年5月10日更正)

冒泡排序总是将比较结果较小的元素与其前一个元素进行交换。我们可以考虑一下。这个算法中的元素越晚，切换到前一个位置的概率就越小(因为每次“冒泡”的几率只有50%)。原始数组按照从小到大的顺序排序，所以测试平均值的结果自然是越往后越大(因为后面的大数出现在前面的概率越小)。

让我们改变另一个算法，这次我们使用插入排序：

函数insertionSort(arr，compare){ var len=arr . length；for(var I=0；我透镜；I){ for(var j=I ^ 1；j lenj ){ if(compare(arr[i]，arr[j])0){ var tmp=arr[I]；arr[I]=arr[j]；arr[j]=tmp；} } }返回arr}函数shuffle(arr){ return insertionSort(arr，function(){ return math . random()-0.5；});}var arr=[0，1，2，3，4，5，6，7，8，9]；var res=[0，0，0，0，0，0，0，0，0，0，0]；var t=10000for(var I=0；I t；I){ var sorted=shuffle(arr . slice(0))；sorted.forEach(function(o，I){ RES[I]=o；});}res=res.map(函数(o){ return o/t；});console . log(RES)；因为insert排序找到后一个大的数与前一个交换，所以这次的结果与冒泡排序相反，测试平均值的结果自然会越来越小。原因和上面差不多。对于插入排序，后面的数字更有可能随机切换到前面。

因此，我们可以看到，即使是成对交换排序算法，随机分布也是大不相同的。除了每两个位置比较一次的排序算法外，大多数排序算法的时间复杂度都在O(n)到O(n2)之间，元素之间的比较次数通常远小于n(n-1)/2，这意味着有些元素根本没有比较的机会(也没有随机交换的可能)，这些排序随机排序算法自然不是真正的随机。

让我们更改上面的代码并使用快速排序：

函数quickSort(arr，compare){ arr=arr . slice(0)；if(arr.length=1)返回arrvar mid=arr[0]，rest=arr . slice(1)；var左=[]，右=[]；for(var I=0；我休息。i ){ if(compare(rest[i]，mid)0){ right . push(rest[I])；} else { left . push(rest[I])；} }返回快速排序(左，比较)。concat([mid])。concat(快速排序(右，比较))；}函数shuffle(arr){ return quick sort(arr，function(){ return math . random()-0.5；});}var arr=[0，1，2，3，4，5，6，7，8，9]；var res=[0，0，0，0，0，0，0，0，0，0，0]；var t=10000for(var I=0；I t；I){ var sorted=shuffle(arr . slice(0))；sorted.forEach(function(o，I){ RES[I]=o；});}res=res.map(函数(o){ return o/t；});console . log(RES)；快速排序不是每两个元素进行比较，其概率分布也不是随机的。

因此，我们可以得出这样的结论：通过Array.prototype.sort的随机交换来随机排列数组所得到的结果不一定是随机的，而是取决于排序算法是如何实现的。用JavaScript内置的排序算法进行排序通常不是完全随机的。

经典随机排列

所有空间复杂度为O(1)的排序算法的时间复杂度都在O(nlogn)到O(n2)之间，因此在不考虑算法结果误差的情况下，使用排序进行随机交换比较慢。事实上，对于随机排列数组元素，有一个O(n)复杂度的经典算法：

函数shuffle(arr){ var len=arr . length；for(var I=0；I len-1；I){ var idx=math . floor(math . random()*(len-I))；var temp=arr[idx]；arr[idx]=arr[len-I-1]；arr[len-I-1]=temp；}返回arr}在上面的算法中，我们在每个循环中从前面的len-i元素中随机取一个位置，用len-i元素交换这个元素，并迭代直到i=len-1。

我们也可以测试这个算法的随机性：

函数shuffle(arr){ var len=arr . length；for(var I=0；I len-1；I){ var idx=math . floor(math . random()*(len-I))；var temp=arr[idx]；arr[idx]=arr[len-I-1]；arr[len-I-1]=temp；}返回arr}var arr=[0，1，2，3，4，5，6，7，8，9]；var res=[0，0，0，0，0，0，0，0，0，0，0]；var t=10000for(var I=0；I t；I){ var sorted=shuffle(arr . slice(0))；sorted.forEach(function(o，I){ RES[I]=o；});}res=res.map(函数(o){ return o/t；});console . log(RES)；从结果可以看出，这种算法的随机结果应该是一致的。然而，我们的测试方法有一个小问题。我们只测试了平均值。实际上，平均值法只是均匀分布的一个必要条件，而不是充分条件，平均值法不一定是均匀分布。但是不用担心，其实我们可以简单的从数学上证明这个算法的随机性。

用数学归纳法证明随机性

随机化n的数量：

首先，我们考虑n=2的情况。根据算法，很明显有1/2的概率两个数字交换，有1/2的概率两个数字不交换。因此，对于n=2的情况，每个位置出现元素的概率为1/2，满足随机性要求。

假设有I个数字，当i=2时，算法的随机性满足要求，即每个数字出现在每个位置的概率为1/I。

根据我们的算法，每个数字都有1/(I ^ 1)的概率在第一个循环中交换到最后，所以每个元素出现在最后一位的概率是1/(I ^ 1)。而且每个数字也有I/(I ^ 1)的概率，没有交换到最后。如果不交换，则从第二个周期开始，I号将恢复为随机的。根据2的假设。它们出现在I个位置的概率是1/i，因此，每个数字出现在前I个位的任何一个中的概率是(i/(i 1)) * (1/i)=1/(i 1)，也是1/(i 1)。

根据1。2.3.对于任意n=2，通过该算法，每个元素出现在n个位置中任意一个的概率为1/n。

摘要

一个优秀的算法应该同时满足正确的结果和高效率。不幸的是，使用Array.prototype.sort方法不能满足这两个条件。因此，当我们需要实现类似洗牌的功能时，应该采用巧妙的经典洗牌算法，它不仅完全随机，而且效率高。

除了收获这样的算法之外，我们还应该认真对待这种动手分析和解决问题的思路，把我们学过而被大多数人遗忘的数学捡起来(比如数学归纳法，一种经典的证明方法)。

如有问题，请与作者讨论~

以上就是本文的全部内容。希望本文的内容能给大家的学习或工作带来一些帮助，也希望多多支持我们！