看板 Ajax作者 s25g5d4 (function(){})()標題 Re: [js] chrome 的 Math.random() 好固定的感覺時間 Mon Jun 26 21:21:30 2017
上面原因有人解釋過了
這裡提供一個簡單的解法：
Array(N)
.fill()
.map( (v,i) => [ ++i, Math.random() ] )
.sort( (a,b) => a[1] - b[1] )
.map( (x) => x[0] )
寫成白話文(?)的話大概是這樣
var arr = [];
for (var i = 0; i < N; ++i) {
arr[i] = [ i + 1, Math.random() ];
}
arr.sort(function compare(a, b) {
return a[1] - b[1];
});
for (i = 0; i < N; ++i) {
arr[i] = arr[i][0];
}
如果要用已經填好資料的陣列來做的話可以這樣：
// dataArray contains some elements
dataArray
.map( (e) => [e, Math.random()] )
.sort( (a, b) => a[1] - b[1] )
.map( (e) => e[0] )
翻成白話文：
for (var i = 0; i < dataArray.length; ++i) {
dataArray[i] = [ dataArray[i], Math.random() ];
}
dataArray.sort(function compare(a, b) {
return a[1] - b[1];
}
for (i = 0; i < dataArray.length; ++i) {
dataArray[i] = dataArray[i][0];
}
原解法作者：Dominic Wu
討論串：
https://www.facebook.com/groups/f2e.tw/permalink/1326307397406622/
--
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.33.238.141
※ 文章代碼(AID): #1PKGfU2N (Ajax)
※ 文章網址: https://www.ptt.cc/bbs/Ajax/M.1498483294.A.097.html
※ 同主題文章:
Re: [ js ] chrome 的 Math.random() 好固定的感覺
06-26 21:21 s25g5d4.
推 LPH66: 這就是我推文說的「給每個元素一個亂數值再用它排序」方法之所以要這樣做的原因還是在於比較函式的全序性
雖然誰大誰小要隨機, 但給定兩個東西要回傳一致的結果
*給定同樣的兩個東西
然後其實我還漏講了一個條件是遞移性
也就是你的比較函式必須要能夠當 a>b, b>c 時保證 a>c
很多常見的演算法是靠著這個條件才得以快速排序
這兩個條件單純回傳 1 / -1 的亂數函式是無法達成的1F 06/26 21:38
→ Kenqr: 時間複雜度是O(N)，應該是一般使用的正規方法。
另外下面有人提到類似原原po的方法，但作者自己承認錯了XD11F 06/27 10:16
→ s25g5d4: 其實這解法的優點是可以寫成一行 XD13F 06/27 15:04
→ CaptainH: 寫成一行這麼重要? 簡單的事情何必用複雜的方法做14F 06/28 00:00
推 oToToT: 時間複雜度跟空間複雜度都比較高的做法OAO15F 06/28 13:57
--