关于JavaScript的数组随机排序

JavaScript 开发中有时会遇到要将一个数组随机排序(shuffle)的需求，一个常见的写法是这样：

创新互联公司是专业的十堰网站建设公司，十堰接单;提供网站设计制作、成都网站制作,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行十堰网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

 
 
 
 
    
  
  
  
  
  1. function shuffle(arr) { 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3.    arr.sort(function () { 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5.       return Math.random() - 0.5; 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7.    }); 
    8. 
  
  
  
  
  8.  
    9. 
  
  
  
  
  9. } 
    10.

或者使用更简洁的 ES6 的写法：

 
 
 
 
    
  
  
  
  
  1. function shuffle(arr) { 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3.     arr.sort(() => Math.random() - 0.5); 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5. } 
    6.

我也曾经经常使用这种写法，不久前才意识到，这种写法是有问题的，它并不能真正地随机打乱数组。

问题

看下面的代码，我们生成一个长度为 10 的数组['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']，使用上面的方法将数组乱序，执行多次后，会发现每个元素仍然有很大机率在它原来的位置附近出现。

 
 
 
 
    
  
  
  
  
  1. let n = 10000; 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3. let count = (new Array(10)).fill(0); 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5.   
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7. for (let i = 0; i < n; i ++) { 
    8. 
  
  
  
  
  8.  
    9. 
  
  
  
  
  9.     let arr = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']; 
    10. 
  
  
  
  
  10.  
    11. 
  
  
  
  
  11.     arr.sort(() => Math.random() - 0.5); 
    12. 
  
  
  
  
  12.  
    13. 
  
  
  
  
  13.     count[arr.indexOf('a')]++; 
    14. 
  
  
  
  
  14.  
    15. 
  
  
  
  
  15. } 
    16. 
  
  
  
  
  16.  
    17. 
  
  
  
  
  17.   
    18. 
  
  
  
  
  18.  
    19. 
  
  
  
  
  19. console.log(count); 
    20.

在 Node.JS 6 中执行，输出[ 2891, 2928, 1927, 1125, 579, 270, 151, 76, 34, 19 ](带有一定随机性，每次结果都不同，但大致分布应该一致)，即进行 10000 次排序后，字母'a'(数组中的***个元素)有约 2891 次出现在***个位置、2928 次出现在第二个位置，与之对应的只有 19 次出现在***一个位置。如果把这个分布绘制成图像，会是下面这样：

类似地，我们可以算出字母'f'(数组中的第六个元素)在各个位置出现的分布为[ 312, 294, 579, 1012, 1781, 2232, 1758, 1129, 586, 317 ]，图像如下：

如果排序真的是随机的，那么每个元素在每个位置出现的概率都应该一样，实验结果各个位置的数字应该很接近，而不应像现在这样明显地集中在原来位置附近。因此，我们可以认为，使用形如arr.sort(() => Math.random() - 0.5)这样的方法得到的并不是真正的随机排序。

另外，需要注意的是上面的分布仅适用于数组长度不超过 10 的情况，如果数组更长，比如长度为 11，则会是另一种分布。比如：

 
 
 
 
    
  
  
  
  
  1. let a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k']; // 长度为11 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3. let n = 10000; 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5. let count = (new Array(a.length)).fill(0); 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7.   
    8. 
  
  
  
  
  8.  
    9. 
  
  
  
  
  9. for (let i = 0; i < n; i ++) { 
    10. 
  
  
  
  
  10.  
    11. 
  
  
  
  
  11.     let arr = [].concat(a); 
    12. 
  
  
  
  
  12.  
    13. 
  
  
  
  
  13.     arr.sort(() => Math.random() - 0.5); 
    14. 
  
  
  
  
  14.  
    15. 
  
  
  
  
  15.     count[arr.indexOf('a')]++; 
    16. 
  
  
  
  
  16.  
    17. 
  
  
  
  
  17. } 
    18. 
  
  
  
  
  18.  
    19. 
  
  
  
  
  19.   
    20. 
  
  
  
  
  20.  
    21. 
  
  
  
  
  21. console.log(count); 
    22.

在 Node.JS 6 中执行，结果为[ 785, 819, 594, 679, 941, 1067, 932, 697, 624, 986, 1876 ]，其中***个元素'a'的分布图如下：

sort_03

分布不同的原因是 v8 引擎中针对短数组和长数组使用了不同的排序方法(下面会讲)。可以看到，两种算法的结果虽然不同，但都明显不够均匀。

国外有人写了一个Shuffle算法可视化的页面，在上面可以更直观地看到使用arr.sort(() => Math.random() - 0.5)的确是很不随机的。

探索

看了一下ECMAScript中关于Array.prototype.sort(comparefn)的标准，其中并没有规定具体的实现算法，但是提到一点：

Calling comparefn(a,b) always returns the same value v when given a specific pair of values a and b as its two arguments.

也就是说，对同一组a、b的值，comparefn(a, b)需要总是返回相同的值。而上面的() => Math.random() - 0.5(即(a, b) => Math.random() - 0.5)显然不满足这个条件。

翻看v8引擎数组部分的源码，注意到它出于对性能的考虑，对短数组使用的是插入排序，对长数组则使用了快速排序，至此，也就能理解为什么() => Math.random() - 0.5并不能真正随机打乱数组排序了。(有一个没明白的地方：源码中说的是对长度小于等于 22 的使用插入排序，大于 22 的使用快排，但实际测试结果显示分界长度是 10。)

解决方案

知道问题所在，解决方案也就比较简单了。

方案一

既然(a, b) => Math.random() - 0.5的问题是不能保证针对同一组a、b每次返回的值相同，那么我们不妨将数组元素改造一下，比如将每个元素i改造为：

 
 
 
 
    
  
  
  
  
  1. let new_i = { 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3.     v: i, 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5.     r: Math.random() 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7. }; 
    8.

即将它改造为一个对象，原来的值存储在键v中，同时给它增加一个键r，值为一个随机数，然后排序时比较这个随机数：

 
 
 
 
    
  
  
  
  
  1. arr.sort((a, b) => a.r - b.r); 
    2.

完整代码如下：

 
 
 
 
    
  
  
  
  
  1. function shuffle(arr) { 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3.     let new_arr = arr.map(i => ({v: i, r: Math.random()})); 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5.     new_arr.sort((a, b) => a.r - b.r); 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7.     arr.splice(0, arr.length, ...new_arr.map(i => i.v)); 
    8. 
  
  
  
  
  8.  
    9. 
  
  
  
  
  9. } 
    10. 
  
  
  
  
  10.  
    11. 
  
  
  
  
  11.   
    12. 
  
  
  
  
  12.  
    13. 
  
  
  
  
  13. let a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']; 
    14. 
  
  
  
  
  14.  
    15. 
  
  
  
  
  15. let n = 10000; 
    16. 
  
  
  
  
  16.  
    17. 
  
  
  
  
  17. let count = (new Array(a.length)).fill(0); 
    18. 
  
  
  
  
  18.  
    19. 
  
  
  
  
  19.   
    20. 
  
  
  
  
  20.  
    21. 
  
  
  
  
  21. for (let i = 0; i < n; i ++) { 
    22. 
  
  
  
  
  22.  
    23. 
  
  
  
  
  23.     shuffle(a); 
    24. 
  
  
  
  
  24.  
    25. 
  
  
  
  
  25.     count[a.indexOf('a')]++; 
    26. 
  
  
  
  
  26.  
    27. 
  
  
  
  
  27. } 
    28. 
  
  
  
  
  28.  
    29. 
  
  
  
  
  29.   
    30. 
  
  
  
  
  30.  
    31. 
  
  
  
  
  31. console.log(count); 
    32.

一次执行结果为：[ 1023, 991, 1007, 967, 990, 1032, 968, 1061, 990, 971 ]。多次验证，同时在这儿查看shuffle(arr)函数结果的可视化分布，可以看到，这个方法可以认为足够随机了。

方案二(Fisher–Yates shuffle)

需要注意的是，上面的方法虽然满足随机性要求了，但在性能上并不是很好，需要遍历几次数组，还要对数组进行splice等操作。

考察Lodash 库中的 shuffle 算法，注意到它使用的实际上是Fisher–Yates 洗牌算法，这个算法由 Ronald Fisher 和 Frank Yates 于 1938 年提出，然后在 1964 年由 Richard Durstenfeld 改编为适用于电脑编程的版本。用伪代码描述如下：

 
 
 
 
    
  
  
  
  
  1. -- To shuffle an array a of n elements (indices 0..n-1): 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3. for i from n−1 downto 1 do 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5.      j ← random integer such that 0 ≤ j ≤ i 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7.      exchange a[j] and a[i] 
    8.

一个实现如下(ES6)：

 
 
 
 
    
  
  
  
  
  1. function shuffle(arr) { 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3.     let i = arr.length; 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5.     while (i) { 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7.         let j = Math.floor(Math.random() * i--); 
    8. 
  
  
  
  
  8.  
    9. 
  
  
  
  
  9.         [arr[j], arr[i]]= [arr[i], arr[j]]; 
    10. 
  
  
  
  
  10.  
    11. 
  
  
  
  
  11.     } 
    12. 
  
  
  
  
  12.  
    13. 
  
  
  
  
  13. } 
    14.

或者对应的 ES5 版本：

 
 
 
 
    
  
  
  
  
  1. function shuffle(arr) { 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3.   var i = arr.length, t, j; 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5.   while (i) { 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7.     j = Math.floor(Math.random() * i--); 
    8. 
  
  
  
  
  8.  
    9. 
  
  
  
  
  9.     t = arr[i]; 
    10. 
  
  
  
  
  10.  
    11. 
  
  
  
  
  11.     arr[i] = arr[j]; 
    12. 
  
  
  
  
  12.  
    13. 
  
  
  
  
  13.     arr[j] = t; 
    14. 
  
  
  
  
  14.  
    15. 
  
  
  
  
  15.   } 
    16. 
  
  
  
  
  16.  
    17. 
  
  
  
  
  17. } 
    18.

小结

如果要将数组随机排序，千万不要再用(a, b) => Math.random() - 0.5这样的方法。目前而言，Fisher–Yates shuffle 算法应该是***的选择。 

网站标题：关于JavaScript的数组随机排序
标题来源：http://www.zyruijie.cn/qtweb/news12/1562.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

搜索引擎优化知识

分类信息网站

域名注册　　 　营销型网站建设　　 　四川黔盛装饰　　 　成都网站推广　　 　复盛机电设备　　 　成都400电话申请　　 　校园网站建设方案　　 　移动网站建设　　 　成都法律咨询　　 　温岭熙道网站　　 　背发光字　　 　腾讯香港免备案空间　　 　成都网站制作　　 　重庆网站建设　　 　香港虚拟主机腾讯云　　 　新津网站运维　　 　网站建设开发　　 　南充网站建设　　 　成都定制网站　　 　成都网站设计