鍍金池/ 問答/網(wǎng)絡(luò)安全  HTML/ js數(shù)組實(shí)現(xiàn)隨機(jī)排序

js數(shù)組實(shí)現(xiàn)隨機(jī)排序

js 隨機(jī)排序一個(gè)數(shù)組，sort中是如何執(zhí)行的？

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

Array.prototype.sort在es規(guī)范中只定義了行為，沒有規(guī)定具體排序算法的實(shí)現(xiàn)，因此各個(gè)引擎的實(shí)現(xiàn)有所不同。

對(duì)V8而言，數(shù)組長(zhǎng)度小于10則使用插入排序，否則使用快速排序
https://github.com/v8/v8/blob...

clipboard.png

然后這個(gè)方法在已是過去時(shí)，4月份V8對(duì)array.sort和typedarray.sort進(jìn)行了重寫，理由是更好的性能。用的是一個(gè)叫做torque的語(yǔ)言，貌似是V8自己基于c++開發(fā)的一個(gè)DSL

這是array.sort重寫的commit，可以看出實(shí)現(xiàn)還是跟原來一樣。性能提升源于C++本身的性能優(yōu)勢(shì)。

clipboard.png

2017年4月30日 06:26
編輯回答
帥到炸

樓上的大佬解釋了“sort中是如何執(zhí)行的”，我來回答一下“js隨機(jī)排序一個(gè)數(shù)組”吧。

題主的方法是錯(cuò)的，（至少在Chrome中）幾乎所有元素都會(huì)留在自己本來的位置！

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/

而實(shí)際上，題主的方法到底能不能打亂數(shù)組是依賴于sort的具體實(shí)現(xiàn)的。Chrome的具體實(shí)現(xiàn)請(qǐng)見樓上大佬，不論如何，結(jié)果是不行的。

正確的姿勢(shì)是什么呢？

用lodash的_.shuffle，簡(jiǎn)單，快速，直接，易維護(hù)。

或者，實(shí)現(xiàn)一個(gè)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...

2017年12月21日 04:24