array是什么意思

c++⼆维数组排序_「前端进阶」数组乱序

引⾔

数组乱序指的是：将数组元素的排列顺序随机打乱。

将⼀个数组进⾏乱序处理，是⼀个⾮常简单但是⾮常常⽤的需求。⽐如，“猜你喜欢”、“点击换⼀批”、“中奖⽅案”等等，都可能应

⽤到这样的处理。

sort结合

微软曾在上做过⼀个关于不同浏览器使⽤情况的调查，微软会在页⾯中以随机顺序向⽤户显⽰不同的浏览器。

然⽽每个浏览器出现的位置并不是随机的。IE在最后⼀个位置出现的概率⼤概是50%，Chrome在⼤部分情况下都会出现在浏览器列表的前

三位。

这是怎么回事，不是说好的随机顺序么？

这是他们⽤来做随机shuffle的代码：

(()=>()-0.5);复制代码

乍⼀看，这似乎是⼀个合理的解决⽅案。事实上在使⽤搜索引擎搜索“随机打乱数组”，这种⽅式会是出现最多的答案。

然⽽，这种⽅式并不是真正意思上的乱序，⼀些元素并没有机会相互⽐较，最终数组元素停留位置的概率并不是完全随机的。

来看⼀个例⼦：

/***数组乱序*/functionshuffle(arr){(()=>()-0.5);}复制代码/***⽤于验证shuffle⽅法是否完全随机*/functiontest_shuffle(shuffleFn){//

在这个例⼦中，我们定义了两个函数，shuffle中使⽤sort和()进⾏数组乱序操作；test_shuffle函数定义了⼀个长度为

10的数组['a','b','c','d','e','f','g','h','i','j']，并使⽤传⼊的乱序函数进⾏⼗万次操作，并将数组中每个元素在每个位置出现的次数存放到

变量countObj中，最终将countObj打印出来。

结果如下：

从这个表格中我们能够看出，每个元素在每个位置出现的概率相差很⼤，⽐如元素a，在索引0的位置上出现了19415次，在索引4的位

置上只出现了7026次，元素a在这两个位置出现的次数相差很⼤(相差⼀倍还多)。如果排序真的是随机的，那么每个元素在每个位置出

现的概率都应该⼀样，实验结果各个位置的数字应该很接近，⽽不是像现在这样各个位置的数字相差很⼤。

为什么会有问题呢？这需要从⽅法排序底层说起。

v8在处理sort⽅法时，使⽤了插⼊排序和快排两种⽅案。当⽬标数组长度⼩于10时，使⽤插⼊排序；反之，使⽤快速排序。

其实不管⽤什么排序⽅法，⼤多数排序算法的时间复杂度介于O(n)到O(n²)之间，元素之间的⽐较次数通常情况下要远⼩于n(n-1)/2，也

就意味着有⼀些元素之间根本就没机会相⽐较(也就没有了随机交换的可能)，这些sort随机排序的算法⾃然也不能真正随机。

其实我们想使⽤进⾏乱序，理想的⽅案或者说纯乱序的⽅案是数组中每两个元素都要进⾏⽐较，这个⽐较有50%的交换位置概

率。这样⼀来，总共⽐较次数⼀定为n(n-1)。⽽在sort排序算法中，⼤多数情况都不会满⾜这样的条件。因⽽当然不是完全随机的结果

了。

从插⼊排序来看sort的不完全⽐较

⼀段简单的插⼊排序代码：

functioninrtSort(list=[]){for(leti=1,len=;i=0&&list[j]>temp){list[j+1]=list[j];j=j-1

其原理在于将第⼀个元素视为有序序列，遍历数组，将之后的元素依次插⼊这个构建的有序序列中。

我们来个简单的⽰意图：

我们来具体分析下['a','b','c']这个数组乱序的结果，需要注意的是，由于数组长度⼩于10，所以sort函数内部是使⽤插⼊排序实现的。

演⽰代码为：

varvalues=['a','b','c'];(function(){()-0.5;});复制代码

详细分析如下：

由于插⼊排序将第⼀个元素视为有序的，所以数组的外层循环从i=1开始。此时⽐较a和b，因为()-0.5的结果有

50%的概率⼩于0，有50%的概率⼤于0，所以有50%的概率数组变成['b','a','c']，50%的结果不变，数组依然为['a','b','c']。

假设依然是['a','b','c']，我们再进⾏⼀次分析，接着遍历，i=2，⽐较b和c：

有50%的概率数组不变，依然是['a','b','c']，然后遍历结束。

有50%的概率变成['a','c','b']，因为还没有找到c正确的位置，所以还会进⾏遍历，所以在这50%的概率中⼜会进⾏⼀次⽐较，⽐较a

和c，有50%的概率不变，数组为['a','c','b']，此时遍历结束，有50%的概率发⽣变化，数组变成['c','a','b']。

综上，在['a','b','c']中，有50%的概率会变成['a','b','c']，有25%的概率会变成['a','c','b']，有25%的概率会变成['c','a','b']。

另外⼀种情况['b','a','c']与之分析类似，我们将最终的结果汇总成⼀个表格：

改造sort和()的结合⽅式

我们已然知道sort和()来实现数组乱序所存在的问题，主要是由于缺少每个元素之间的⽐较，那么我们不妨将数组元素改

造⼀下，将其改造为⼀个对象。

letarr=[{val:'a',ram:()},{val:'b',ram:()}//...]复制代码

我们将数组中原来的值保存在对象的val属性中，同时为对象增加⼀个属性ram，值为⼀个随机数。

接下来我们只需要对数组中每个对象的随机数进⾏排序，即可得到⼀个乱序数组。

代码如下：

functionshuffle(arr){letnewArr=(item=>({val:item,ram:()}));((a,b)=>);(0,,...(

将shuffle⽅法应⽤于我们之前实现的验证函数test_shuffle中

test_shuffle(shuffle)复制代码

结果如下：

从表格中我们可以看出，每个元素在每个位置出现的次数已经相差不⼤。

虽然已经满⾜了随机性的要求，但是这种实现⽅式在性能上并不好，需要遍历⼏次数组，并且还要对数组进⾏splice操作。

那么如何⾼性能的实现真正的乱序呢？⽽这就要提到经典的Fisher–Yates算法。

Fisher–Yates

为什么叫Fisher–Yates呢？因为这个算法是由RonaldFisher和FrankYates⾸次提出的。

这个算法其实⾮常的简单，就是将数组从后向前遍历，然后将当前元素与随机位置的元素进⾏交换。结合图⽚来解释⼀下：

⾸先我们有⼀个已经排好序的数组

Step1：第⼀步需要做的就是，从数组末尾开始，选取最后⼀个元素。

在数组⼀共9个位置中，随机产⽣⼀个位置，该位置元素与最后⼀个元素进⾏交换。

Step2：上⼀步中，我们已经把数组末尾元素进⾏随机置换。接下来，对数组倒数第⼆个元素动⼿。在除去已经排好的最后⼀个元素位置

以外的8个位置中，随机产⽣⼀个位置，该位置元素与倒数第⼆个元素进⾏交换。

Step3：理解了前两步，接下来就是依次进⾏，如此简单。

接下来我们⽤代码来实现⼀下Fisher–Yates

functionshuffle(arr){letm=;while(m>1){letindex=(()*m--);[arr[m],arr[index]]=[arr[index],arr[m]]}returnarr;}复制代码

接着我们再⽤之前的验证函数test_shuffle中

test_shuffle(shuffle);复制代码

结果如下：

从表格中我们可以看出，每个元素在每个位置出现的次数相差不⼤，说明这种⽅式满⾜了随机性的要求。

⽽且Fisher–Yates算法只需要通过⼀次遍历即可将数组随机打乱顺序，性能极为优异~~

⾄此，我们找到了将数组乱序操作的最优办法：Fisher–Yates~