js数组实现随机排序

Question

js 随机排序一个数组，sort中是如何执行的？

var arr = [1,2,3,4,5,6,7,8,9,10];
      arr.sort(function(){
          return Math.random() - 0.5;
      })
      console.log(arr);

Answer 1

楼上的大佬解释了“sort中是如何执行的”，我来回答一下“js随机排序一个数组”吧。

题主的方法是错的，（至少在Chrome中）几乎所有元素都会留在自己本来的位置！

Results	slot 0	slot 1	slot 2	slot 3	slot 4	slot 5	slot 6	slot 7	slot 8	slot 9
A's	2919	2889	1924	1120	581	296	141	83	34	13
B's	2925	2859	1901	1104	604	294	165	77	48	23
C's	1883	1951	2259	1689	1030	585	324	165	78	36
D's	1096	1081	1742	2228	1734	1005	592	310	144	68
E's	550	603	1059	1760	2229	1785	1034	564	274	142
F's	306	298	558	993	1738	2319	1817	1064	608	299
G's	161	172	295	569	1056	1718	2346	1915	1131	637
H's	89	80	147	323	575	1127	1731	2595	2068	1265
I's	45	45	82	146	286	564	1234	2015	3144	2439
J's	26	22	33	68	167	307	616	1212	2471	5078

https://jsfiddle.net/rcmp0aLL/

而实际上，题主的方法到底能不能打乱数组是依赖于sort的具体实现的。Chrome的具体实现请见楼上大佬，不论如何，结果是不行的。

正确的姿势是什么呢？

用lodash的_.shuffle，简单，快速，直接，易维护。

或者，实现一个Fisher-Yates算法：

function shuffleArray(array) {
    for (let i = array.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
}

以上fiddle和代码取自StackOverflow https://stackoverflow.com/que...

Answer 2

Array.prototype.sort在es规范中只定义了行为，没有规定具体排序算法的实现，因此各个引擎的实现有所不同。

对V8而言，数组长度小于10则使用插入排序，否则使用快速排序
https://github.com/v8/v8/blob...

然后这个方法在已是过去时，4月份V8对array.sort和typedarray.sort进行了重写，理由是更好的性能。用的是一个叫做torque的语言，貌似是V8自己基于c++开发的一个DSL

这是array.sort重写的commit，可以看出实现还是跟原来一样。性能提升源于C++本身的性能优势。