Re: [ js ] chrome 的 Math.random() 好固定的感覺

看板Ajax作者 (function(){})()時間6年前 (2017/06/26 21:21), 編輯推噓3(3012)
留言15則, 5人參與, 最新討論串3/4 (看更多)
上面原因有人解釋過了 這裡提供一個簡單的解法: 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 ※ 文章網址: https://www.ptt.cc/bbs/Ajax/M.1498483294.A.097.html

06/26 21:38, , 1F
這就是我推文說的「給每個元素一個亂數值再用它排序」方法
06/26 21:38, 1F

06/26 21:39, , 2F
之所以要這樣做的原因還是在於比較函式的全序性
06/26 21:39, 2F

06/26 21:39, , 3F
雖然誰大誰小要隨機, 但給定兩個東西要回傳一致的結果
06/26 21:39, 3F

06/26 21:40, , 4F
*給定同樣的兩個東西
06/26 21:40, 4F

06/26 21:40, , 5F
然後其實我還漏講了一個條件是遞移性
06/26 21:40, 5F

06/26 21:41, , 6F
也就是你的比較函式必須要能夠當 a>b, b>c 時保證 a>c
06/26 21:41, 6F

06/26 21:42, , 7F
很多常見的演算法是靠著這個條件才得以快速排序
06/26 21:42, 7F

06/26 21:43, , 8F
這兩個條件單純回傳 1 / -1 的亂數函式是無法達成的
06/26 21:43, 8F

06/27 10:15, , 9F
用sort處理的時間複雜度是O(NlogN),且需要使用temp array
06/27 10:15, 9F

06/27 10:15, , 10F
06/27 10:15, 10F

06/27 10:16, , 11F
時間複雜度是O(N),應該是一般使用的正規方法。
06/27 10:16, 11F

06/27 10:16, , 12F
另外下面有人提到類似原原po的方法,但作者自己承認錯了XD
06/27 10:16, 12F

06/27 15:04, , 13F
其實這解法的優點是可以寫成一行 XD
06/27 15:04, 13F

06/28 00:00, , 14F
寫成一行這麼重要? 簡單的事情何必用複雜的方法做
06/28 00:00, 14F

06/28 13:57, , 15F
時間複雜度跟空間複雜度都比較高的做法OAO
06/28 13:57, 15F
文章代碼(AID): #1PKGfU2N (Ajax)
文章代碼(AID): #1PKGfU2N (Ajax)