冒泡排序是一種簡(jiǎn)單的排序算法凭戴。它重復(fù)地走訪過要排序的數(shù)列佩抹，一次比較兩個(gè)元素园欣，如果他們的順序錯(cuò)誤就把他們交換過來(lái)帖世。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成沸枯。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端日矫。
算法分析
比較相鄰的元素。如果第一個(gè)比第二個(gè)大辉饱，就交換他們兩個(gè)搬男。對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)彭沼。在這一點(diǎn)缔逛，最后的元素應(yīng)該會(huì)是最大的數(shù)。針對(duì)所有的元素重復(fù)以上的步驟姓惑，除了最后一個(gè)褐奴。持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較于毙。
原始待排序數(shù)組| 6 | 2 | 4 | 1 | 5 | 9 |
第一趟排序(外循環(huán))
第一次兩兩比較6 > 2交換(內(nèi)循環(huán))
交換前狀態(tài)| 6 | 2 | 4 | 1 | 5 | 9 |
交換后狀態(tài)| 2 | 6 | 4 | 1 | 5 | 9 |
第二次兩兩比較,6 > 4交換
交換前狀態(tài)| 2 | 6 | 4 | 1 | 5 | 9 |
交換后狀態(tài)| 2 | 4 | 6 | 1 | 5 | 9 |
第三次兩兩比較,6 > 1交換
交換前狀態(tài)| 2 | 4 | 6 | 1 | 5 | 9 |
交換后狀態(tài)| 2 | 4 | 1 | 6 | 5 | 9 |
第四次兩兩比較,6 > 5交換
交換前狀態(tài)| 2 | 4 | 1 | 6 | 5 | 9 |
交換后狀態(tài)| 2 | 4 | 1 | 5 | 6 | 9 |
第五次兩兩比較,6 < 9不交換
交換前狀態(tài)| 2 | 4 | 1 | 5 | 6 | 9 |
交換后狀態(tài)| 2 | 4 | 1 | 5 | 6 | 9 |
第二趟排序(外循環(huán))
第一次兩兩比較2 < 4不交換
交換前狀態(tài)| 2 | 4 | 1 | 5 | 6 | 9 |
交換后狀態(tài)| 2 | 4 | 1 | 5 | 6 | 9 |
第二次兩兩比較,4 > 1交換
交換前狀態(tài)| 2 | 4 | 1 | 5 | 6 | 9 |
交換后狀態(tài)| 2 | 1 | 4 | 5 | 6 | 9 |
第三次兩兩比較,4 < 5不交換
交換前狀態(tài)| 2 | 1 | 4 | 5 | 6 | 9 |
交換后狀態(tài)| 2 | 1 | 4 | 5 | 6 | 9 |
第四次兩兩比較,5 < 6不交換
交換前狀態(tài)| 2 | 1 | 4 | 5 | 6 | 9 |
交換后狀態(tài)| 2 | 1 | 4 | 5 | 6 | 9 |
第三趟排序(外循環(huán))
第一次兩兩比較2 > 1交換
交換后狀態(tài)| 2 | 1 | 4 | 5 | 6 | 9 |
交換后狀態(tài)| 1 | 2 | 4 | 5 | 6 | 9 |
第二次兩兩比較,2 < 4不交換
交換后狀態(tài)| 1 | 2 | 4 | 5 | 6 | 9 |
交換后狀態(tài)| 1 | 2 | 4 | 5 | 6 | 9 |
第三次兩兩比較,4 < 5不交換
交換后狀態(tài)| 1 | 2 | 4 | 5 | 6 | 9 |
交換后狀態(tài)| 1 | 2 | 4 | 5 | 6 | 9 |
第四趟排序(外循環(huán))無(wú)交換
第五趟排序(外循環(huán))無(wú)交換
排序完畢,輸出最終結(jié)果1 2 4 5 6 9
詳細(xì)代碼請(qǐng)參考Algorithm敦冬。參考代碼比文字好理解。
