【演算】氣泡排序法- Bubble Sort - Infinite Loop

直到所有資料排序完成為止。

其原理的虛擬碼大致如下： Function bubbleSort(Type data[1..n]) Index i, j ... skiptomain| skiptosidebar Home Articles Comments Guestbook Login Viewshoutbox ShoutMixchatwidget 3月07,2010 【演算】氣泡排序法-BubbleSort 張貼者: Unknown @ 13:09 |標籤: 演算 　　氣泡排序法（bubblesort）是排序演算法（sortingalgorithm）中較簡易的一種。

其運作的原理是藉由逐次比較相鄰的兩筆資料，並依照排序條件（由大至小或由小至大）交換資料直到排序完成為止。

　　假設現在我們需要將n筆資料A1、A2、......、An由小排到大。

　　一開始，我們需要先比較A1與A2兩筆資料的大小。

若是A1>A2，則交換兩筆資料；接著比較A2與A3。

若是A2>A3，則交換兩筆資料；以此類推，一直到比較完An-1與An為止。

　　這樣就完了嗎？當然還沒。

到目前為止，我們只確定An是n筆資料中最大的數字。

　　接下來，重複剛剛的動作：比較A1與A2、A2與A3、A3與A4、......，不同的是，這一次只需要比較到An-2與An-1即可。

到目前為止，我們可以確定An-1是n筆資料中次大的數字。

　　接著就繼續重複同樣的動作，便能確定每一輪比較中的最大資料，皆在這些資料的最後面。

直到所有資料排序完成為止。

　　其原理的虛擬碼大致如下： FunctionbubbleSort(Typedata[1..n]) Indexi,j; Forifromnto2do Forjfrom1toi-1do Ifdata[j]>data[j+1]then Exchangedata[j]anddata[j+1] End 　　讓我們舉個實際的例子來說明。

若是我們現在要將以下這些資料由大排到小： 143679502 　　則第一輪的比較與交換過程如下： 431679502 436179502 436791502 436795012 436795021 　　第二輪的比較與交換過程如下： 436795021 437965021 437950621 437950621 　　接下來以此類推。

　　由此可以看到，資料中較小的一筆會藉由交換慢慢「浮」到資料頂端，其「氣泡排序」之名也是因此而來。

　　若是我們分析在最差情況下（即所有資料的順序剛好完全相反，因為我們必須在每一輪迴圈，藉由不斷交換兩筆資料的動作，把最前頭的資料移到最後面），使用氣泡排序法將n筆資料排序的敘述執行次數（註1）： FunctionbubbleSort(Typedata[1..n]) Indexi,j;//1 Forifromnto2do//n-1 Forjfrom1toi-1do//n(n-1)/2 Ifdata[j]>data[j+1]then//n(n-1)/2 Exchangedata[j]anddata[j+1]//n(n-1)/2 End 　　可得出所有敘述的執行次數總和為：W(n)=1+(n-1)+n(n-1)/2+n(n-1)/2+n(n-1)/2=(3n2-n)/2∈Ο(n2)，為一個平方時間（quadratictime）的演算法。

　　而在最好的情況下（即所有資料都為已排序狀態，因為不需要進行任何一次交換動作）： FunctionbubbleSort(Typedata[1..n]) Indexi,j;//1 Forifromnto2do//n-1 Forjfrom1toi-1do//n(n-1)/2 Ifdata[j]>data[j+1]then//n(n-1)/2 Exchangedata[j]anddata[j+1]//0 End 　　所有敘述的執行次數總和為：B(n)=1+(n-1)+n(n-1)/2+n(n-1)/2+0=n2∈Ο(n2)。

複雜度依舊為平方時間。

　　對於一種排序演算法而言，這樣複雜度是相當沒有效率的。

因此這個方法多半只是被拿來簡單的解釋排序概念，而不是拿來實際應用。

註1.其中的n(n-1)/2是由(n-1)+(n-2)+(n-3)+...+1加總化簡而來。

RSS 3 回覆: pojan 提到... 第二段有點怪怪的，應該是A1>A2，兩筆資料才要交換吧？如果是由小到大排序的話 2009年4月6日凌晨2:10 Unknown 提到... 確實是我寫錯了,感謝您的指正:) 2009年4月6日下午1:01 Unknown 提到... 3qq 2014年10月24日下午2:47 張貼留言 較新的文章 較舊的文章 首頁 訂閱： 張貼留言(Atom) InfiniteLoop©2008.BlogdesignbyBlogcut|ConvertedbyFernandooo1(Randomness) AboutMe InfiniteLoop：寫程式就是如此，一直寫下去，不知盡頭在那。

檢視我的完整簡介 Labels 介紹 (9) 目錄 (8) 作品 (16) 筆記 (8) 解題 (69) 演算 (25) 演講 (1) 語言 (8) 翻譯 (24) 轉貼 (7) 雜記 (6) ACM (50) C (4) C++ (37) FLOLAC (1) JS (2) PHP (3) Qt (30) USACO (6) Verilog (5) YUI (2) Search Archive Archive 三月2008(10) 四月2008(19) 五月2008(17) 六月2008(2) 七月2008(6) 八月2008(11) 九月2008(4) 十月2008(3) 十一月2008(12) 十二月2008(6) 一月2009(7) 二月2009(31) 四月2009(22) 七月2009(2) 三月2010(11) 四月2010(2) 七月2010(2) 九月2010(2)