推 barry70490: 比較好奇是 mod√n 還是mod n 11/21 22:54
推 sarsman: 已知S至少有√n個物品，感覺mod √n比較合理，做四次 11/21 23:56
→ bighb69738: 我原本也像s大這麼想 但不確定行否 11/22 00:21
→ barry70490: 好像不是√n欸 剛剛查了一下是n 11/22 00:44
→ barry70490: 然後回應你的問題 應該是只有這個方法因為其他不管怎 11/22 00:46
→ barry70490: 麼做都沒有辦法O(|S|) 11/22 00:46
推 JKLee: To big大,若S中的元素大小介於1~sqrt n之間,你寫在紙上的 11/22 02:42
→ JKLee: 方法就無效 11/22 02:42
→ bighb69738: 好的我了解了 我時間不應該寫 n^1/2 因為用radix sort 11/22 08:07
→ bighb69738: 還是跳脫不出 線性時間 11/22 08:07
推 sarsman: 請問J大，為何會無效呢@@ 11/22 14:34
推 JKLee: 對不起，我錯了。把big大寫在紙上的方法改成5個pass應該就 11/22 21:59
→ JKLee: 可以了 11/22 21:59
→ JKLee: 令n=4,key值範圍是1~16.使用LSD排序,共有√4=2個桶子. 11/23 00:23
→ JKLee: 16以2進制表示為10000,共5位數.所以LSD排序須5個Pass. 11/23 00:23
→ sarsman: 的確需要5次 11/23 00:59