[理工] 基本氣泡排序問題

看板Grad-ProbAsk作者 (Wayne)時間8年前 (2018/02/06 23:11), 編輯推噓8(8推 0噓 3→)
留言11則, 4人參與, 8年前最新討論串1/1
最近在複習資料結構，看到以下這題 題目： 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://www.ptt.cc/bbs/Grad-ProbAsk/M.1517929882.A.569.html
推
02/06 23:22, 8年前 , 1F
比較7+6+5+4+3+2+1
02/06 23:22, 1F
推
02/06 23:26, 8年前 , 2F
pass1~pass7 交換了6 4 3 2 2 0 0次
02/06 23:26, 2F
推
02/06 23:30, 8年前 , 3F
02/06 23:30, 3F
推
02/06 23:37, 8年前 , 4F
樓上Huffman
02/06 23:37, 4F
推
02/06 23:40, 8年前 , 5F
我到剛剛D大的回文才知道huffman的時間複雜度是O(blown)
02/06 23:40, 5F
→
02/06 23:42, 8年前 , 6F
O(nlogn)
02/06 23:42, 6F
推
02/06 23:51, 8年前 , 7F
我剛code出來是17次
02/06 23:51, 7F
→
02/07 00:14, 8年前 , 8F
手動追蹤吧
02/07 00:14, 8F
→
02/07 00:32, 8年前 , 9F
02/07 00:32, 9F
推
02/08 05:36, 8年前 , 10F
是問比幾次 不是換幾次
02/08 05:36, 10F
推
02/08 13:55, 8年前 , 11F
哇靠 今天中央考這題
02/08 13:55, 11F
‣ 更多 wayneshiau 的文章
文章代碼(AID): #1QUSMQLf (Grad-ProbAsk)