最近看了一篇很有意思的文章：关于JavaScript中数组的随机排序，作者是oldj学长。文章指出了我们以前“随机排序数组”的经典方式存在的问题，受益匪浅。本文将以更详细的资料和更多样化的代码演示进行阐述。并尝试使用“Fisher–Yatesshuffle”洗牌算法求最终答案。在多个熟悉的场景中乱序处理一个数组是一个很简单但是很常见的需求。例如，“猜猜你喜欢什么”、“点击更改一批”、“中奖方案”等，都可以应用此类处理。包括我自己在写代码的时候，也确实遇到过。一般比较经典流行的方案是：对对象数组使用array.sort()方法，传入一个比较函数（comparisonfunction），这个比较函数随机返回一个[-0.5,0.5]之间的值：varnumbers=[12,4,16,3];numbers.sort(function(){return.5-Math.random();});这里不解释这样做的理论基础。不懂的可以学习一下JS中排序功能的使用方法。有毒的array.sort方法正如oldj的前辈文章指出的那样。其实用这种方法打乱数组是有问题的。为此，我写了一个脚本来验证。并可视化。强烈建议读者去Github看看，clone下来自己试试。在脚本中，我有varletters=['A','B','C','D','E','F','G','H','I','J'];使用array.sort方法对字母等数组进行了10,000次乱序处理，并将乱序的每一次结果存储在countings中。结果在页面输出：varcountings=[{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0}];varletters=['A','B','C','D','E','F','G','H','I','J'];for(vari=0;i<10000;i++){varr=['A','B','C','D','E','F','G','H','I','J'].sort(function(){return.5-Math.random();});for(varj=0;j<=9;j++){计数[j][r[j]]++;}}for(vari=0;i<=9;i++){for(varj=0;j<=9;j++){document.getElementById('results').rows[i+1].cells[j+1].firstChild.data=countings[i][letters[j]];}}结果如图：统计每个元素乱序后的结果。如果点击“重新计算”按钮，可以进行10000次的多次采样实验。无论你点击按钮多少次，你都会发现整体紊乱后的结果绝对不是“完全随机”的。比如元素A有很大概率出现在数组头部，元素J有很大概率出现在数组尾部，所有元素都有很大概率停留在初始位置。由此大致可以断定，使用array.sort方法进行乱序处理肯定是有问题的。底层的array.sort方法是如何实现的？但是为什么会有问题呢？这就需要从最底层的array.sort方法说起。在Chromev8引擎的源码中，可以清楚的看到v8在处理sort方法的时候，使用了插入排序和快速排序两种方案。当目标数组长度小于10时，使用插入排序；否则，使用快速排序。Chrome的v8结合使用了InsertionSort和QuickSort。也就是说，如果数组的长度少于10个元素，它会使用InsertionSort。事实上，无论采用何种排序方式，大多数排序算法的时间复杂度都在O(n)之间，O(n2)之间，元素之间的比较次数通常远小于n(n-1)/2，也就是说有些元素根本没有机会比较（不存在随机交换的可能性），这些排序随机排序算法自然不可能是真正随机的。怎么理解上面的句子？实际上，我们想使用array.sort进行随机排序。理想的解决方案或纯随机程序是比较数组中的每两个元素。这种比较有50%的概率调换位置。这样，总的比较次数一定是n(n-1)。在sort排序算法中，大多数情况下是不会满足这样的条件的。所以当然这不是一个完全随机的结果。顺便说一句，关于v8引擎的排序方案，源码是用JS实现的，非常方便前端程序员阅读。其中，对应不同的数组长度，采用了不同的快速排序和插入排序的方法。同时使用了很多性能优化的技巧，尤其是快速排序的pivot选择很有意思。有兴趣的读者不妨研究一下。真正意义上的无序实现真正意义上的无序并不难。我们首先要绕过不稳定的array.sort方法。在计算机科学中，有一个特殊的算法：洗牌算法Fisher–Yatesshuffle。如果您天生对算法很慢，请不要惊慌。下面我就一步步来实现，相信大家一定看懂了。让我们从整体上看一下所有的代码实现。总共只有10行：Array.prototype.shuffle=function(){varinput=this;对于(vari=input.length-1;i>=0;i--){varrandomIndex=Math.floor(Math.random()*(i+1));变种itemAtIndex=输入[随机索引];输入[随机索引]=输入[i];输入[i]=itemAtIndex；}返回输入；}vartempArray=[1,2,3,4,5,6,7,8,9,10]tempArray.shuffle();console.log(tempArray);分析：首先我们有一个排序数组：Step1：第一步需要做的是从数组的末尾选择最后一个元素。在数组总共9个位置中，随机产生一个位置，这个位置的元素与最后一个元素交换。Step2：在上一步中，我们随机替换了数组末尾的元素。接下来，处理数组的倒数第二个元素。在除最后一个已排好元素的位置外的8个位置中，随机生成一个位置，将这个位置的元素与倒数第二个元素交换。Step3：理解了前两部分之后，接下来就是依次进行，就这么简单。上述乱序实现的方法是基于Fisher-Yatesshuffle算法。接下来，我们需要开动脑筋，完成一个无序的计划。其实这并不难，关键在于如何产生真实的无序。因为经常生成的东西并不是完全乱序的，关于这一点读者可以参考文章TheDangerofNa?veté。下面来看看社区刘娃勇的一系列进阶方案：functionshuffle(array){varcopy=[],n=array.length,i;while(n){i=Math.floor(Math.random()*array.length);if(iinarray){copy.push(array[i]);删除数组[i]；n--;}}returncopy;}分析：我们创??建了一个copy数组，然后遍历了target数组，将它的元素复制到copy数组中，并从target数组中删除了该元素，这样下次可以跳过序号遍历。这种实现方式的问题在于，即使一个序号上的元素已经被处理过，由于随机函数生成的数字是随机的，所有被处理过的元素的序号可能会在后续的循环中继续出现。一是效率问题，二是逻辑问题。有可能永远用不完。改进的方案是：functionshuffle(array){varcopy=[],n=array.length,i;while(n){i=Math.floor(Math.random()*n--);copy.push(array.splice(i,1)[0]);}returncopy;}改进的方法是使用Array的splice()方法在处理完一个元素后将其从目标数组中移除，同时也更新目标数组的长度。这样，下一次遍历就会从新的长度开始，不会重复这种情况。当然这个方案也有缺点：比如我们创建了一个复制数组返回，在内存中开辟了新的空间。然而，这可以完全避免：functionshuffle(array){varm=array.length,t,i;while(m){i=Math.floor(Math.random()*m--);t=数组[m]；数组[m]=数组[i]；数组[i]=t;}returnarray;}有趣的是，这样的实现完全等价于上述洗牌算法Fisher–Yatesshuffle的方案。小结本文分析了“数组乱序”这样一个简单但有趣的需求场景。对这个场景的深入分析，让我们体会到了JS和计算机算法中的一些奥秘。文章简单提到了V8引擎对array.sort的处理，洗牌算法Fisher–Yates等，希望对读者有所启发。快乐编码！PS：作者的Github仓库，欢迎通过代码以各种形式交流。最近看了一篇很有意思的文章：关于JavaScript数组的随机排序，作者是oldj的前辈。文章指出了我们以前“随机排序数组”的经典方式存在的问题，受益匪浅。本文将以更详细的资料和更多样化的代码演示进行阐述。并尝试使用“Fisher–Yatesshuffle”洗牌算法求最终答案。在多个熟悉的场景中乱序处理一个数组是一个很简单但是很常见的需求。例如，“猜猜你喜欢什么”、“点击更改一批”、“中奖方案”等，都可以应用此类处理。包括我自己在写代码的时候，也确实遇到过。一般比较经典流行的方案是：对对象数组使用array.sort()方法，传入一个比较函数（comparisonfunction），这个比较函数随机返回一个[-0.5,0.5]之间的值：varnumbers=[12,4,16,3];numbers.sort(function(){return.5-Math.random();});这里不解释这样做的理论基础。不懂的可以学习一下JS中排序功能的使用方法。有毒的array.sort方法正如oldj的前辈文章指出的那样。其实用这种方法打乱数组是有问题的。为此，我写了一个脚本来验证。并可视化。强烈建议读者去Github看看，clone下来自己试试。在脚本中，我有varletters=['A','B','C','D','E','F','G','H','I','J'];使用array.sort方法对字母等数组进行了10,000次乱序处理，并将乱序的每一次结果存储在countings中。结果在页面输出：varcountings=[{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0}];varletters=['A','B','C','D','E','F','G','H','I','J'];for(vari=0;i<10000;i++){varr=['A','B','C','D','E','F','G','H','I','J'].sort(function(){return.5-Math.random();});for(varj=0;j<=9;j++){计数[j][r[j]]++;}}for(vari=0;i<=9;i++){for(varj=0;j<=9;j++){document.getElementById('results').rows[i+1].cells[j+1].firstChild.data=countings[i][letters[j]];}}结果如图：统计每个元素乱序后的结果。如果点击“重新计算”按钮，可以进行10000次的多次采样实验。无论你点击按钮多少次，你都会发现整体紊乱后的结果绝对不是“完全随机”的。比如元素A有很大概率出现在数组头部，元素J有很大概率出现在数组尾部，所有元素都有很大概率停留在初始位置。由此大致可以断定，使用array.sort方法进行乱序处理肯定是有问题的。底层的array.sort方法是如何实现的？但是为什么会有问题呢？这就需要从最底层的array.sort方法说起。在Chromev8引擎的源码中，可以清楚的看到v8在处理sort方法的时候，使用了插入排序和快速排序两种方案。当目标数组长度小于10时，使用插入排序；否则，使用快速排序。Chrome的v8结合使用了InsertionSort和QuickSort。也就是说，如果数组的长度少于10个元素，它会使用InsertionSort。事实上，无论采用何种排序方式，大多数排序算法的时间复杂度都在O(n)之间，O(n2)之间，元素之间的比较次数通常远小于n(n-1)/2，也就是说有些元素根本没有机会比较（不存在随机交换的可能性），这些排序随机排序算法自然不可能是真正随机的。怎么理解上面的句子？实际上，我们想使用array.sort进行随机排序。理想的解决方案或纯随机程序是比较数组中的每两个元素。这种比较有50%的概率调换位置。这样，总的比较次数一定是n(n-1)。在sort排序算法中，大多数情况下是不会满足这样的条件的。所以当然这不是一个完全随机的结果。顺便说一句，关于v8引擎的排序方案，源码是用JS实现的，非常方便前端程序员阅读。其中，对应不同的数组长度，采用了不同的快速排序和插入排序的方法。同时使用了很多性能优化的技巧，尤其是快速排序的pivot选择很有意思。有兴趣的读者不妨研究一下。真正意义上的无序实现真正意义上的无序并不难。我们首先要绕过不稳定的array.sort方法。在计算机科学中，有一个特殊的算法：洗牌算法Fisher–Yatesshuffle。如果您天生对算法很慢，请不要惊慌。下面我就一步步来实现，相信大家一定看懂了。让我们从整体上看一下所有的代码实现。总共只有10行：Array.prototype.shuffle=function(){varinput=this;对于(vari=input.length-1;i>=0;i--){varrandomIndex=Math.floor(Math.random()*(i+1));变种itemAtIndex=输入[随机索引];输入[随机索引]=输入[i];输入[i]=itemAtIndex；}返回输入；}vartempArray=[1,2,3,4,5,6,7,8,9,10]tempArray.shuffle();console.log(tempArray);分析：首先我们有一个排序数组：Step1：第一步需要做的是从数组的末尾选择最后一个元素。在数组总共9个位置中，随机产生一个位置，这个位置的元素与最后一个元素交换。Step2：在上一步中，我们随机替换了数组末尾的元素。接下来，处理数组的倒数第二个元素。在除最后一个已排好元素的位置外的8个位置中，随机生成一个位置，将这个位置的元素与倒数第二个元素交换。Step3：理解了前两部分之后，接下来就是依次进行，就这么简单。上述乱序实现的方法是基于Fisher-Yatesshuffle算法。接下来，我们需要开动脑筋，完成一个无序的计划。其实这并不难，关键在于如何产生真实的无序。因为经常生成的东西并不是完全乱序的，关于这一点读者可以参考文章TheDangerofNa?veté。下面来看看社区刘娃勇的一系列进阶方案：functionshuffle(array){varcopy=[],n=array.length,i;while(n){i=Math.floor(Math.random()*array.length);if(iinarray){copy.push(array[i]);删除数组[i]；n--;}}returncopy;}分析：我们创??建了一个copy数组，然后遍历了target数组，将它的元素复制到copy数组中，并从target数组中删除了该元素，这样下次可以跳过序号遍历。这种实现方式的问题在于，即使一个序号上的元素已经被处理过，由于随机函数生成的数字是随机的，所有被处理过的元素的序号可能会在后续的循环中继续出现。一是效率问题，二是逻辑问题。有可能永远用不完。改进的方案是：functionshuffle(array){varcopy=[],n=array.length,i;while(n){i=Math.floor(Math.random()*n--);copy.push(array.splice(i,1)[0]);}returncopy;}改进的方法是使用Array的splice()方法在处理完一个元素后将其从目标数组中移除，同时也更新目标数组的长度。这样，下一次遍历就会从新的长度开始，不会重复这种情况。当然这个方案也有缺点：比如我们创建了一个复制数组返回，在内存中开辟了新的空间。然而，这可以完全避免：functionshuffle(array){varm=array.length,t,i;while(m){i=Math.floor(Math.random()*m--);t=数组[m]；数组[m]=数组[i]；数组[i]=t;}returnarray;}有趣的是，这样的实现完全等价于上述洗牌算法Fisher–Yatesshuffle的方案。小结本文分析了“数组乱序”这样一个简单但有趣的需求场景。对这个场景的深入分析，让我们体会到了JS和计算机算法中的一些奥秘。文章简单提到了V8引擎对array.sort的处理，洗牌算法Fisher–Yates等，希望对读者有所启发。快乐编码！PS：作者的Github仓库，欢迎通过代码以各种形式交流。百度知识搜索部前端持续招聘中，有意者速联系。..
