冒泡排序
跳去導覽
跳去搵嘢
冒泡排序(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 )
攷[編輯]
- ↑ 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.
- ↑ Astrachan, Owen (2003). "Bubble sort: an archaeological algorithmic analysis" (PDF). ACM SIGCSE Bulletin. 35 (1): 1–5.