[理工] [資結] sorting

看板Grad-ProbAsk作者 (0 0)時間11年前 (2013/01/24 22:18), 編輯推噓11(11推 0噓 14→)
留言25則, 12人參與, 最新討論串1/1
二個SORTING的問題 1. Which sorting algo is best for sorted array? Insertion sort,selection sort,bubble sort ,quick sort ,or merge sort? 我是選 quick sort. 因為他的Avg time 是O(nlogn) 但是 merge 也是,不知道我選的正不正確 2. http://imgur.com/LIJzODA
此圖中的 (a) 問題 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 1.170.127.41
→
01/24 22:19, , 1F
sorted array中最差的表現就是Quick sort
01/24 22:19, 1F
→
01/24 22:20, , 2F
是因為會大量的移動嗎?
01/24 22:20, 2F
→
01/24 22:21, , 3F
大量的比較次數
01/24 22:21, 3F
→
01/24 22:22, , 4F
下面那個就是選擇排序法
01/24 22:22, 4F
→
01/24 22:23, , 5F
那這樣選selection sort呢?
01/24 22:23, 5F
推
01/24 22:23, , 6F
merge 因為最差都有nlogn
01/24 22:23, 6F
→
01/24 22:23, , 7F
喔喔~感謝
01/24 22:23, 7F
推
01/24 22:34, , 8F
1.insertion 2.感覺是bubble,把大的都往上擠
01/24 22:34, 8F
→
01/24 22:36, , 9F
沒事 我改變想法
01/24 22:36, 9F
推
01/24 22:45, , 10F
1選insertion感覺怪怪的＠＠sorted並不一定是由小到大吧
01/24 22:45, 10F
推
01/24 22:51, , 11F
arrary感覺是依序排序，我的話會選Bubble sort
01/24 22:51, 11F
推
01/24 22:55, , 12F
第二題的話圖是先來先排序，感覺是Insertion sort
01/24 22:55, 12F
推
01/24 23:06, , 13F
第二題感覺是selection吧 從最前面開始排 一直排到整個
01/24 23:06, 13F
→
01/24 23:06, , 14F
完成
01/24 23:06, 14F
推
01/24 23:09, , 15F
同上，仔細看點的位置都不同，表示有交換
01/24 23:09, 15F
→
01/24 23:10, , 16F
所以才把大的值往上丟，位置才會都不同
01/24 23:10, 16F
→
01/24 23:11, , 17F
應該是選擇排序 QQ
01/24 23:11, 17F
推
01/24 23:21, , 18F
Quick在選PK的時候如果選到max或min 就會是最差
01/24 23:21, 18F
推
01/24 23:28, , 19F
第二題是selection 我看課本的
01/24 23:28, 19F
推
01/25 00:14, , 20F
看動畫好理解XD
01/25 00:14, 20F
→
01/25 00:14, , 21F
01/25 00:14, 21F
推
01/25 10:35, , 22F
第二題是bubble嗎?在array裡data一定由小到大排嘛?
01/25 10:35, 22F
→
01/25 10:36, , 23F
第一題才對 = = 另外 第二題是selection
01/25 10:36, 23F
→
01/25 12:10, , 24F
1應該不會是bubble或insert 因為有可能遇到最糟狀況:大→小
01/25 12:10, 24F
→
01/25 12:23, , 25F
quick也遇到最糟狀況 而select必O(n^d) 所以是merge sort
01/25 12:23, 25F
‣ 更多 diesnow 的文章
文章代碼(AID): #1H0KAp7n (Grad-ProbAsk)