[理工] [資結] 102交大資演第9題

看板Grad-ProbAsk作者kurc (辛拉麵)時間11年前 (2015/01/28 13:19)推噓7(7推 0噓 6→)

留言13則, 5人參與討論串1/1

http://i.imgur.com/X33UFng.png

一開始看以為是quicksort 但是下去追蹤後完全不是這一回事整個都沒排序到的感覺Orz 我自己做的部分: (這部分是錯的，因為沒注意到第二個else if沒i++的結果) 第一次partiton，pivot是4，結束後 1 0 0 1 4 2 3 1 0 2 ↑ ↑ low(值為-1) high(指向data[5]) 補充正解（感謝galapous大提醒盲點）第一次 parition 後：4 1 3 2 0 1 0 0 1 2 low=-1 high=1 第二次：　　　　　　　3 2 2 1 1 1 0 0 0 low=1 high=6 第三次：　　　　　　　3 2 　　　　　　　low=0 high=2 第四次：　　　　　　　　　　　　　0 0 0 low=-1 high=3　 final content : 4 3 2 2 1 1 1 0 0 0 (Ans(1)) partition invoked: 4次　(Ans(2)) 這個是由大排到小的quick sort:　最差時間複雜度　size^2 (Ans(3)) 附上昨天怒打的驗證ＸＤ　http://goo.gl/ePgIJ0 給大家參考囉，如果有問題可以再討論 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.164.7.202 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1422422380.A.AEC.html

推

APE36

01/28 13:26, , 1^F

01/28 13:26, 1^F

→

APE36

01/28 13:27, , 2^F

01/28 13:27, 2^F

推

galapous

01/28 14:29, , 3^F

01/28 14:29, 3^F