跳去內容

冒泡排序

出自維基百科,自由嘅百科全書
用冒泡排序將一個有 8 個數字嘅數列排好

冒泡排序英文bubble sort或sinking sort)係一種用嚟將一個數列入面啲數字由細至大排好演算法,做法係喺每一步攞相鄰嘅兩個數比較,將兩個數由細到大排好,再將個過程做若干次,做到成個數列都排好嗮為止。原則上,冒泡排序並唔好用-喺最壞情況下要行成 咁多步先行得完,所以喺現實,冒泡排序多數都淨係俾人用嚟做電腦科學上嘅教育用途[1][2]

例如如果用冒泡排序同 5, 1, 4, 2, 8 呢個數列排序嘅話:

第一回合
( 5 1 4 2 8 ) → ( 1 5 4 2 8 ),5 > 1,所以將 5 同 1 位置互換,
( 1 5 4 2 8 ) → ( 1 4 5 2 8 ),5 > 4,所以將 5 同 4 位置互換,
( 1 4 5 2 8 ) → ( 1 4 2 5 8 ),5 > 2,所以將 5 同 2 位置互換,
( 1 4 2 5 8 ) → ( 1 4 2 5 8 ),5 < 8,所以 5 同 8 唔使郁。
第二回合
( 1 4 2 5 8 ) → ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 ),查實到咗呢一步,個數列經已排好咗,但段演算法要再重新睇多次個數列先至知呢一點。
第三回合
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

文化

[編輯]

喺2007年一個問答環節入邊,前Google CEO Eric Schmidt問當時嘅美國總統候選人奧巴馬將一百萬個整數排序最好嘅方法係乜,奧巴馬諗咗一陣答:「冒泡排序應該唔係一個好方法。」(I think the bubble sort would be the wrong way to go.)[3][4]

[編輯]
  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Problem 2-2, pg.40.
  2. Astrachan, Owen (2003). "Bubble sort: an archaeological algorithmic analysis" (PDF). ACM SIGCSE Bulletin. 35 (1): 1–5.
  3. Lai Stirland, Sarah (2007-11-14). "Obama Passes His Google Interview". Wired. 喺2020-10-27搵到.
  4. Barack Obama, Eric Schmidt (Nov 14, 2007). Barack Obama | Candidates at Google (Youtube) (英文). Mountain View, CA 94043 The Googleplex: Talks at Google. 時間 23:20. 原著 (Video)喺September 7, 2019歸檔. 喺Sep 18, 2019搵到.{{cite AV media}}: CS1 maint: location (link)