作者wayneshiau (Wayne)
看板Grad-ProbAsk
標題[理工] 基本氣泡排序問題
時間Tue Feb 6 23:11:20 2018
最近在複習資料結構，看到以下這題
題目：
How many comparisons are required to sort the sequence of numbers
'27, 61, 18, 17, 32, 4, 11, 52' in nondecreasing order by using
Bubble Sort?
想請問有比較快速的解法嘛？
因為這題他不是worst case，所以應該不是
7+6+5+4+3+2+1次吧？
謝謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.36.225.110
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1517929882.A.569.html
1F：推 Huffman: 比較7+6+5+4+3+2+1 02/06 23:22
2F：推 Huffman: pass1~pass7 交換了6 4 3 2 2 0 0次 02/06 23:26
4F：推 agag5123: 樓上Huffman 02/06 23:37
5F：推 Huffman: 我到剛剛D大的回文才知道huffman的時間複雜度是O(blown) 02/06 23:40
6F：→ Huffman: O(nlogn) 02/06 23:42
7F：推 Jyery: 我剛code出來是17次 02/06 23:51
8F：→ Jyery: 手動追蹤吧 02/07 00:14
10F：推 rbkrbk: 是問比幾次 不是換幾次 02/08 05:36
11F：推 Jyery: 哇靠 今天中央考這題 02/08 13:55