[問題] 排序的問題 - 分籃排序會比較快嗎?

看板C_and_CPP作者 (ppppk)時間12年前 (2013/05/25 09:05), 編輯推噓2(2推 0噓 6→)
留言8則, 6人參與, 最新討論串1/1
這個問題是一般algorithm的問題 不過別板都沒什麼人 所以就在這裡發問了 我要產生10000000000000個數值 然後再排序 假設我大概知道這些數值的中間值 情況一 先全部放一籃 然後整籃做排序 情況二 數值產生的時候 就以假設的中間值為準 大的放一籃 小的放另一籃 然後兩籃再各自排序 情況二排序本身會比較快 但是數值產生時要比較一次才能決定要放哪一籃 全部的程序加起來 會比情況一快嗎? 謝謝~~~ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.255.224.90
推
05/25 11:49, , 1F
你去查快速排序
05/25 11:49, 1F
→
05/25 11:50, , 2F
如果你有疑慮，基本上實際測試較準
05/25 11:50, 2F
→
05/25 13:02, , 3F
如果中間值剛好假設到邊邊就會差不多。
05/25 13:02, 3F
→
05/25 13:05, , 4F
如果真的有 10T 個資料，還是放棄吧 ;)
05/25 13:05, 4F
→
05/25 13:19, , 5F
感覺很有可能遇到Quick Sort的最糟情況欸@_@
05/25 13:19, 5F
→
05/25 13:19, , 6F
試試看HeapSort之類的吧@_@
05/25 13:19, 6F
推
05/25 15:51, , 7F
10T 就用external merge sort 囉
05/25 15:51, 7F
→
05/25 18:42, , 8F
radix sort
05/25 18:42, 8F
‣ 更多 ppppk 的文章
文章代碼(AID): #1He0vla5 (C_and_CPP)