基本思想
将被排序的記錄數組r[0..n-1]垂直排列，每個記錄r[i]看作是重量為r[i].key的氣泡。根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組r：凡掃描到違反本原則的輕氣泡，就使其 向上”飄浮”。如此反複進行，直到最後任何兩個氣泡都是輕者在上，重者在下為止。
具體過程，如下所示：
初始狀态：r[0..n-1]為無序區。
第一趟掃描：從無序區底部向上依次比較相鄰的兩個氣泡的重量，若發現輕者在下、重者 在上，則交換二者的位置，即依次比較(r[n-1], r[n-2])、(r[n-2], r[n-3])、…、(r[1], r[0])；對于每對氣泡(r[j+1], r[j])，若r[j+1].key第一趟掃描完畢時，”最輕”的氣泡就飄浮到該區間的頂部，即關鍵字最小的記錄被放在最高位置r[0]上。
第二趟掃描：掃描r[1..n-1]。掃描完畢時，”次輕”的氣泡飄浮到r[1]的位置上……最後，經過n-1趟掃描可得到有序區r[0..n-1]。
注意：
第i趟掃描時，r[0..i-1]和r[i..n-1]分别為目前的有序區和無序區。掃描仍是從無序區底 部向上直至該區頂部。掃描完畢時，該區中最輕氣泡飄浮到頂部位置r[i]上，結果是r[0..i]變為新的有序區。
算法實作
冒泡排序算法，java實作，代碼如下所示：
<code>01</code>
<code>public</code> <code>abstract</code> <code>class</code> <code>sorter {</code>
<code>02</code>
<code></code><code>public</code> <code>abstract</code> <code>void</code> <code>sort(</code><code>int</code><code>[] array);</code>
<code>03</code>
<code>}</code>
<code>04</code>
<code>05</code>
<code>public</code> <code>class</code> <code>bubblesorter</code><code>extends</code> <code>sorter {</code>
<code>06</code>
<code>07</code>
<code></code><code>@override</code>
<code>08</code>
<code></code><code>public</code> <code>void</code> <code>sort(</code><code>int</code><code>[] array) {</code>
<code>09</code>
<code></code><code>int</code> <code>tmp;</code><code>// 用于交換資料的暫存單元</code>
<code>10</code>
<code></code><code>for</code> <code>(</code><code>int</code> <code>i = array.length -</code><code>1</code><code>; i >=</code><code>0</code><code>; i--) {</code><code>// 将數組最小索引一端視為“水面”</code>
<code>11</code>
<code></code><code>// 将數組最小索引一端視為“水底”，“氣泡”從“水底”向“水面”上浮</code>
<code>12</code>
<code></code><code>// 因為i每增加1，就有一個上浮到最終排序位置，是以，隻需要對1~i個元素進行交換排序</code>
<code>13</code>
<code></code><code>for</code> <code>(</code><code>int</code> <code>j =</code><code>1</code><code>; j <= i; j++) {</code>
<code>14</code>
<code></code><code>if</code> <code>(array[j -</code><code>1</code><code>] < array[j]) {</code><code>// 如果上浮過程中發現存在比目前元素小的，就交換，将小的交換到“水面”</code>
<code>15</code>
<code></code><code>tmp = array[j -</code><code>1</code><code>];</code>
<code>16</code>
<code></code><code>array[j -</code><code>1</code><code>] = array[j];</code>
<code>17</code>
<code></code><code>array[j] = tmp;</code>
<code>18</code>
<code></code><code>}</code>
<code>19</code>
<code>20</code>
<code>21</code>
<code>22</code>
冒泡排序算法，python實作，代碼如下所示：
<code>class</code> <code>sorter:</code>
<code></code><code>'''</code>
<code></code><code>abstract sorter class, which provides shared methods being used by</code>
<code></code><code>subclasses.</code>
<code></code><code>__metaclass__</code><code>=</code> <code>abcmeta</code>
<code></code>
<code></code><code>@abstractmethod</code>
<code></code><code>def</code> <code>sort(</code><code>self</code><code>, array):</code>
<code></code><code>pass</code>
<code>class</code> <code>bubblesorter(sorter):</code>
<code></code><code>bubble sorter</code>
<code></code><code>length</code><code>=</code> <code>len</code><code>(array)</code>
<code></code><code>i</code><code>=</code> <code>length</code><code>-</code> <code>1</code>
<code></code><code>while</code> <code>i></code><code>=</code><code>0</code><code>:</code>
<code></code><code>j</code><code>=</code> <code>1</code>
<code></code><code>while</code> <code>j<</code><code>=</code><code>i:</code>
<code></code><code>if</code> <code>array[j</code><code>-</code><code>1</code><code>]<array[j]:</code>
<code>23</code>
<code></code><code>array[j</code><code>-</code><code>1</code><code>], array[j]</code><code>=</code> <code>array[j], array[j</code><code>-</code><code>1</code><code>]</code>
<code>24</code>
<code></code><code>j</code><code>=</code> <code>j</code><code>+</code> <code>1</code>
<code>25</code>
<code></code><code>i</code><code>=</code> <code>i</code><code>-</code> <code>1</code>
排序過程
冒泡排序的執行過程如下：
首先，将待排序數組視為一個無序區。
從數組一端開始，讓元素小的逐漸移動到另一端，稱為氣泡的上浮過程，直到整個數組變成一個有序區。
下面，我們通過例子還說明排序過程。假設待排序數組為array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，數組大小為20。
将數組最小索引一端視為“水底”，排序過程如下所示：
<code>{94,34,76,26,12,9,37,55,76,37,5,68,83,90,37,12,65,76,49, 0}</code>
<code>{94,76,34,26,12,37,55,76,37,9,68,83,90,37,12,65,76,49, 5,0}</code>
<code>{94,76,34,26,37,55,76,37,12,68,83,90,37,12,65,76,49, 9,5,0}</code>
<code>{94,76,34,37,55,76,37,26,68,83,90,37,12,65,76,49, 12,9,5,0}</code>
<code>{94,76,37,55,76,37,34,68,83,90,37,26,65,76,49, 12,12,9,5,0}</code>
<code>{94,76,55,76,37,37,68,83,90,37,34,65,76,49, 26,12,12,9,5,0}</code>
<code>{94,76,76,55,37,68,83,90,37,37,65,76,49, 34,26,12,12,9,5,0}</code>
<code>{94,76,76,55,68,83,90,37,37,65,76,49, 37,34,26,12,12,9,5,0}</code>
<code>{94,76,76,68,83,90,55,37,65,76,49, 37,37,34,26,12,12,9,5,0}</code>
<code>{94,76,76,83,90,68,55,65,76,49, 37,37,37,34,26,12,12,9,5,0}</code>
<code>{94,76,83,90,76,68,65,76,55, 49,37,37,37,34,26,12,12,9,5,0}</code>
<code>{94,83,90,76,76,68,76,65, 55,49,37,37,37,34,26,12,12,9,5,0}</code>
<code>{94,90,83,76,76,76,68, 65,55,49,37,37,37,34,26,12,12,9,5,0}</code>
<code>{94,90,83,76,76,76, 68,65,55,49,37,37,37,34,26,12,12,9,5,0}</code>
<code>{94,90,83,76,76, 76,68,65,55,49,37,37,37,34,26,12,12,9,5,0}</code>
<code>{94,90,83,76, 76,76,68,65,55,49,37,37,37,34,26,12,12,9,5,0}</code>
<code>{94,90,83, 76,76,76,68,65,55,49,37,37,37,34,26,12,12,9,5,0}</code>
<code>{94,90, 83,76,76,76,68,65,55,49,37,37,37,34,26,12,12,9,5,0}</code>
<code>{94, 90,83,76,76,76,68,65,55,49,37,37,37,34,26,12,12,9,5,0}</code>
<code>{ 94,90,83,76,76,76,68,65,55,49,37,37,37,34,26,12,12,9,5,0}</code>
上圖是冒泡排序過程中執行各趟排序，整個數組中元素的位置資訊：左上半部分是無序區，右下半部分是有序區。
算法分析
時間複雜度
最好情況：有序
數組元素需要兩兩比較，一趟排序完成。
比較次數：n-1
交換次數：0
最壞情況：逆序
需要進行n-1趟排序。
有序區數組大小為0時：比較n-1次，交換n-1次，移動3(n-1)次；
有序區數組大小為1時：比較n-2次，交換n-2次，移動3(n-2)次；
……
有序區數組大小為n-3時：比較2次，交換2次，移動3*2次；
有序區數組大小為n-2時：比較1次，交換1次，移動3*1次；
比較次數為：1+2+……+(n-1) = n(n-1)/2
移動次數為：3(1+2+……+(n-1)) = 3n(n-1)/2
綜上，冒泡排序的時間複雜度為o(n2)。
空間複雜度
冒泡排序屬于交換排序，在排序過程中，隻需要用到一個用來執行元素交換的變量即可。是以，空間複雜度為o(1)。
排序穩定性
冒泡排序是就地排序。
冒泡排序是穩定的。
![Cloud Studio初體驗[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)