冒泡排序

出自維基百科,自由嘅百科全書
跳去導覽 跳去搵嘢
用冒泡排序將一個有 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 )

[編輯]

  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.