作者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/cn.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