{"action":"created","issue":{"url":"https://api.github.com/repos/mqyqingfeng/Blog/issues/51","repository_url":"https://api.github.com/repos/mqyqingfeng/Blog","labels_url":"https://api.github.com/repos/mqyqingfeng/Blog/issues/51/labels{/name}","comments_url":"https://api.github.com/repos/mqyqingfeng/Blog/issues/51/comments","events_url":"https://api.github.com/repos/mqyqingfeng/Blog/issues/51/events","html_url":"https://github.com/mqyqingfeng/Blog/issues/51","id":264798569,"node_id":"MDU6SXNzdWUyNjQ3OTg1Njk=","number":51,"title":"JavaScript专题之乱序","user":{"login":"mqyqingfeng","id":11458263,"node_id":"MDQ6VXNlcjExNDU4MjYz","avatar_url":"https://avatars3.githubusercontent.com/u/11458263?v=4","gravatar_id":"","url":"https://api.github.com/users/mqyqingfeng","html_url":"https://github.com/mqyqingfeng","followers_url":"https://api.github.com/users/mqyqingfeng/followers","following_url":"https://api.github.com/users/mqyqingfeng/following{/other_user}","gists_url":"https://api.github.com/users/mqyqingfeng/gists{/gist_id}","starred_url":"https://api.github.com/users/mqyqingfeng/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mqyqingfeng/subscriptions","organizations_url":"https://api.github.com/users/mqyqingfeng/orgs","repos_url":"https://api.github.com/users/mqyqingfeng/repos","events_url":"https://api.github.com/users/mqyqingfeng/events{/privacy}","received_events_url":"https://api.github.com/users/mqyqingfeng/received_events","type":"User","site_admin":false},"labels":[{"id":618327137,"node_id":"MDU6TGFiZWw2MTgzMjcxMzc=","url":"https://api.github.com/repos/mqyqingfeng/Blog/labels/%E4%B8%93%E9%A2%98%E7%B3%BB%E5%88%97","name":"专题系列","color":"0071b5","default":false}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":13,"created_at":"2017-10-12T02:57:14Z","updated_at":"2018-12-12T07:33:50Z","closed_at":null,"author_association":"OWNER","body":"## 乱序\r\n\r\n乱序的意思就是将数组打乱。\r\n\r\n嗯，没有了，直接看代码吧。\r\n\r\n## Math.random\r\n\r\n一个经常会遇见的写法是使用 Math.random()：\r\n\r\n```js\r\nvar values = [1, 2, 3, 4, 5];\r\n\r\nvalues.sort(function(){\r\n    return Math.random() - 0.5;\r\n});\r\n\r\nconsole.log(values)\r\n```\r\n\r\n`Math.random() - 0.5` 随机得到一个正数、负数或是 0，如果是正数则降序排列，如果是负数则升序排列，如果是 0 就不变，然后不断的升序或者降序，最终得到一个乱序的数组。\r\n\r\n看似很美好的一个方案，实际上，效果却不尽如人意。不信我们写个 demo 测试一下：\r\n\r\n```js\r\nvar times = [0, 0, 0, 0, 0];\r\n\r\nfor (var i = 0; i < 100000; i++) {\r\n    \r\n    let arr = [1, 2, 3, 4, 5];\r\n    \r\n    arr.sort(() => Math.random() - 0.5);\r\n    \r\n    times[arr[4]-1]++;\r\n\r\n}\r\n\r\nconsole.log(times)\r\n```\r\n\r\n测试原理是：将 `[1, 2, 3, 4, 5]` 乱序 10 万次，计算乱序后的数组的最后一个元素是 1、2、3、4、5 的次数分别是多少。\r\n\r\n一次随机的结果为：\r\n\r\n```js\r\n[30636, 30906, 20456, 11743, 6259]\r\n```\r\n\r\n该结果表示 10 万次中，数组乱序后的最后一个元素是 1 的情况共有 30636 次，是 2 的情况共有 30906 次，其他依此类推。\r\n\r\n我们会发现，最后一个元素为 5 的次数远远低于为 1 的次数，所以这个方案是有问题的。\r\n\r\n可是我明明感觉这个方法还不错呐？初见时还有点惊艳的感觉，为什么会有问题呢？\r\n\r\n是的！我很好奇！\r\n\r\n## 插入排序\r\n\r\n如果要追究这个问题所在，就必须了解 sort 函数的原理，然而 ECMAScript 只规定了效果，没有规定实现的方式，所以不同浏览器实现的方式还不一样。\r\n\r\n为了解决这个问题，我们以 v8 为例，v8 在处理 sort 方法时，当目标数组长度小于 10 时，使用插入排序；反之，使用快速排序和插入排序的混合排序。\r\n\r\n所以我们来看看 v8 的源码，因为是用 JavaScript 写的，大家也是可以看懂的。\r\n\r\n源码地址：[https://github.com/v8/v8/blob/master/src/js/array.js](https://github.com/v8/v8/blob/master/src/js/array.js)\r\n\r\n为了简化篇幅，我们对 `[1, 2, 3]` 这个数组进行分析，数组长度为 3，此时采用的是插入排序。\r\n\r\n插入排序的源码是：\r\n\r\n```js\r\nfunction InsertionSort(a, from, to) {\r\n    for (var i = from + 1; i < to; i++) {\r\n        var element = a[i];\r\n        for (var j = i - 1; j >= from; j--) {\r\n            var tmp = a[j];\r\n            var order = comparefn(tmp, element);\r\n            if (order > 0) {\r\n                a[j + 1] = tmp;\r\n            } else {\r\n                break;\r\n            }\r\n        }\r\n        a[j + 1] = element;\r\n    }\r\n};\r\n```\r\n\r\n其原理在于将第一个元素视为有序序列，遍历数组，将之后的元素依次插入这个构建的有序序列中。\r\n\r\n我们来个简单的示意图：\r\n\r\n![插入排序](https://github.com/mqyqingfeng/Blog/raw/master/Images/sort/insertion.gif)\r\n\r\n## 具体分析\r\n\r\n明白了插入排序的原理，我们来具体分析下 [1, 2, 3] 这个数组乱序的结果。\r\n\r\n演示代码为：\r\n\r\n```js\r\nvar values = [1, 2, 3];\r\n\r\nvalues.sort(function(){\r\n    return Math.random() - 0.5;\r\n});\r\n```\r\n\r\n注意此时 sort 函数底层是使用插入排序实现，InsertionSort 函数的 from 的值为 0，to 的值为 3。\r\n\r\n我们开始逐步分析乱序的过程：\r\n\r\n因为插入排序视第一个元素为有序的，所以数组的外层循环从 `i = 1` 开始，a[i] 值为 2，此时内层循环遍历，比较 `compare(1, 2)`，因为 `Math.random() - 0.5` 的结果有 50% 的概率小于 0 ，有 50% 的概率大于 0，所以有 50% 的概率数组变成 [2, 1, 3]，50% 的结果不变，数组依然为 [1, 2, 3]。\r\n\r\n假设依然是 [1, 2, 3]，我们再进行一次分析，接着遍历，`i = 2`，a[i] 的值为 3，此时内层循环遍历，比较 `compare(2, 3)`：\r\n\r\n有 50% 的概率数组不变，依然是 `[1, 2, 3]`，然后遍历结束。\r\n\r\n有 50% 的概率变成 [1, 3, 2]，因为还没有找到 3 正确的位置，所以还会进行遍历，所以在这 50% 的概率中又会进行一次比较，`compare(1, 3)`，有 50% 的概率不变，数组为 [1, 3, 2]，此时遍历结束，有 50% 的概率发生变化，数组变成 [3, 1, 2]。\r\n\r\n综上，在 [1, 2, 3] 中，有 50% 的概率会变成 [1, 2, 3]，有 25% 的概率会变成 [1, 3, 2]，有 25% 的概率会变成 [3, 1, 2]。\r\n\r\n另外一种情况 [2, 1, 3] 与之分析类似，我们将最终的结果汇总成一个表格：\r\n\r\n<table class=\"table table-bordered table-striped table-condensed\">  \r\n    <tr>\r\n        <th>数组</th>\r\n        <th>i = 1</th>\r\n        <th>i = 2</th>\r\n        <th>总计</th>\r\n    </tr>  \r\n    <tr>  \r\n        <td rowspan=\"6\">[1, 2, 3]</td>\r\n        <td rowspan=\"3\">50% [1, 2, 3]</td>\r\n         <td>50% [1, 2, 3]</td>\r\n         <td>25% [1, 2, 3]</td>\r\n    </tr>\r\n    <tr>  \r\n        <td>25% [1, 3, 2]</td>\r\n        <td>12.5% [1, 3, 2]</td>\r\n    </tr>\r\n    <tr>  \r\n        <td>25% [3, 1, 2]</td>\r\n        <td>12.5% [3, 1, 2]</td>\r\n    </tr>  \r\n    <tr>  \r\n        <td rowspan=\"3\">50% [2, 1, 3]</td>\r\n        <td>50% [2, 1, 3]</td>\r\n         <td>25% [2, 1, 3]</td>\r\n    </tr>\r\n    <tr>  \r\n        <td>25% [2, 3, 1]</td>\r\n        <td>12.5% [2, 3, 1]</td>\r\n    </tr>\r\n    <tr>  \r\n        <td>25% [3, 2, 1]</td>\r\n        <td>12.5% [3, 2, 1]</td>\r\n    </tr>\r\n</table>\r\n\r\n为了验证这个推算是否准确，我们写个 demo 测试一下：\r\n\r\n```js\r\nvar times = 100000;\r\nvar res = {};\r\n\r\nfor (var i = 0; i < times; i++) {\r\n    \r\n    var arr = [1, 2, 3];\r\n    arr.sort(() => Math.random() - 0.5);\r\n    \r\n    var key = JSON.stringify(arr);\r\n    res[key] ? res[key]++ :  res[key] = 1;\r\n}\r\n\r\n// 为了方便展示，转换成百分比\r\nfor (var key in res) {\r\n    res[key] = res[key] / times * 100 + '%'\r\n}\r\n\r\nconsole.log(res)\r\n```\r\n\r\n这是一次随机的结果：\r\n\r\n![Math random 效果演示](https://github.com/mqyqingfeng/Blog/raw/master/Images/shuffle/mathRandom.png)\r\n\r\n我们会发现，乱序后，`3` 还在原位置(即 [1, 2, 3] 和 [2, 1, 3]) 的概率有 50% 呢。\r\n\r\n所以根本原因在于什么呢？其实就在于在插入排序的算法中，当待排序元素跟有序元素进行比较时，一旦确定了位置，就不会再跟位置前面的有序元素进行比较，所以就乱序的不彻底。\r\n\r\n那么如何实现真正的乱序呢？而这就要提到经典的 Fisher–Yates 算法。\r\n\r\n## Fisher–Yates\r\n\r\n为什么叫 Fisher–Yates 呢？ 因为这个算法是由 Ronald Fisher 和 Frank Yates 首次提出的。\r\n\r\n话不多说，我们直接看 JavaScript 的实现：\r\n\r\n```js\r\nfunction shuffle(a) {\r\n    var j, x, i;\r\n    for (i = a.length; i; i--) {\r\n        j = Math.floor(Math.random() * i);\r\n        x = a[i - 1];\r\n        a[i - 1] = a[j];\r\n        a[j] = x;\r\n    }\r\n    return a;\r\n}\r\n```\r\n\r\n原理很简单，就是遍历数组元素，然后将当前元素与以后随机位置的元素进行交换，从代码中也可以看出，这样乱序的就会更加彻底。\r\n\r\n如果利用 ES6，代码还可以简化成：\r\n\r\n```js\r\nfunction shuffle(a) {\r\n    for (let i = a.length; i; i--) {\r\n        let j = Math.floor(Math.random() * i);\r\n        [a[i - 1], a[j]] = [a[j], a[i - 1]];\r\n    }\r\n    return a;\r\n}\r\n```\r\n\r\n还是再写个 demo 测试一下吧：\r\n\r\n```js\r\nvar times = 100000;\r\nvar res = {};\r\n\r\nfor (var i = 0; i < times; i++) {\r\n    var arr = shuffle([1, 2, 3]);\r\n\r\n    var key = JSON.stringify(arr);\r\n    res[key] ? res[key]++ :  res[key] = 1;\r\n}\r\n\r\n// 为了方便展示，转换成百分比\r\nfor (var key in res) {\r\n    res[key] = res[key] / times * 100 + '%'\r\n}\r\n\r\nconsole.log(res)\r\n```\r\n\r\n这是一次随机的结果：\r\n\r\n![Fisher–Yates 效果演示](https://github.com/mqyqingfeng/Blog/raw/master/Images/shuffle/fisher-yates.png)\r\n\r\n真正的实现了乱序的效果！\r\n\r\n## 专题系列\r\n\r\nJavaScript专题系列目录地址：[https://github.com/mqyqingfeng/Blog](https://github.com/mqyqingfeng/Blog)。\r\n\r\nJavaScript专题系列预计写二十篇左右，主要研究日常开发中一些功能点的实现，比如防抖、节流、去重、类型判断、拷贝、最值、扁平、柯里、递归、乱序、排序等，特点是研(chao)究(xi) underscore 和 jQuery 的实现方式。\r\n\r\n如果有错误或者不严谨的地方，请务必给予指正，十分感谢。如果喜欢或者有所启发，欢迎 star，对作者也是一种鼓励。"},"comment":{"url":"https://api.github.com/repos/mqyqingfeng/Blog/issues/comments/446490236","html_url":"https://github.com/mqyqingfeng/Blog/issues/51#issuecomment-446490236","issue_url":"https://api.github.com/repos/mqyqingfeng/Blog/issues/51","id":446490236,"node_id":"MDEyOklzc3VlQ29tbWVudDQ0NjQ5MDIzNg==","user":{"login":"inottn","id":18509404,"node_id":"MDQ6VXNlcjE4NTA5NDA0","avatar_url":"https://avatars2.githubusercontent.com/u/18509404?v=4","gravatar_id":"","url":"https://api.github.com/users/inottn","html_url":"https://github.com/inottn","followers_url":"https://api.github.com/users/inottn/followers","following_url":"https://api.github.com/users/inottn/following{/other_user}","gists_url":"https://api.github.com/users/inottn/gists{/gist_id}","starred_url":"https://api.github.com/users/inottn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/inottn/subscriptions","organizations_url":"https://api.github.com/users/inottn/orgs","repos_url":"https://api.github.com/users/inottn/repos","events_url":"https://api.github.com/users/inottn/events{/privacy}","received_events_url":"https://api.github.com/users/inottn/received_events","type":"User","site_admin":false},"created_at":"2018-12-12T07:33:50Z","updated_at":"2018-12-12T07:33:50Z","author_association":"NONE","body":"@Xing-He \r\n\r\nECMAScript没有定义 `sort` 使用哪种排序算法，实际排序算法取决于浏览器实现的javascript引擎。\r\n\r\n如果使用 `Math.random() - 0.5` 这样的随机判断，**维持原来数组顺序的几率会更高**这个结论是基于使用了**插入排序算法**得到的。\r\n\r\n我在Chrome、Firefox、Safari三个浏览器下运行这段代码，得到的运行结果都相差很大。"}}
{"actor":{"display_login":"inottn"}}