普考申論題
106年
[統計] 資料處理概要
第 二 題
📖 題組：
二、資料之鍵值為 27, 12, 9, 60, 55, 39, 22，請以氣泡排序法排序：
二、資料之鍵值為 27, 12, 9, 60, 55, 39, 22，請以氣泡排序法排序：
📝 此題為申論題，共 2 小題
小題 (二)
在最佳和最壞情況下之時間複雜度分別為何？（10 分）
思路引導 VIP
看到時間複雜度分析題，首先回想該演算法（氣泡排序）的運作機制與極端條件。最壞情況通常是資料完全反序，需考慮總比較次數的數學級數總和；最佳情況則是資料已排序，務必提及『加入旗標（Flag）提早中斷』的改良機制，才能正確導出 O(n) 的結論。
小題 (一)
寫出排序的過程及其結果。（10 分）
思路引導 VIP
看到氣泡排序法，應立刻聯想到其核心運作機制為「相鄰元素兩兩比較，若反序則交換」。解題時，務必先宣告預設的排序方向（通常為由小到大），並逐一列出每個回合（Pass）掃描結束後陣列的狀態，以展現每一次將未排序中最大值推至尾端的演算法軌跡。