[TOC]
## 算法原理
> 冒泡排序（Bubble Sort，臺灣譯為：泡沫排序或氣泡排序）是一種簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。
冒泡排序算法的流程如下：
1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。
3. 針對所有的元素重復以上的步驟，除了最后一個。
4. 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
由于它的簡潔，冒泡排序通常被用來對于程序設計入門的學生介紹算法的概念。
圖片來自維基百科
## 實例分析
以數組 arr = [5, 1, 4, 2, 8] 為例說明，加粗的數字表示每次循環要比較的兩個數字：
第一次外循環
(?**5**?**1**?4 2 8 ) → (?**1**?**5**?4 2 8 )， 5 > 1 交換位置
( 1?**5**?**4**?2 8 ) → ( 1?**4**?**5**?2 8 )， 5 > 4 交換位置
( 1 4?**5**?**2**?8 ) → ( 1 4?**2**?**5**?8 )， 5 > 2 交換位置
( 1 4 2?**5**?**8**?) → ( 1 4 2?**5**?**8**?)， 5 < 8 位置不變
第二次外循環（除開最后一個元素8，對剩余的序列）
(?**1**?**4**?2 5 8 ) → (?**1**?**4**?2 5 8 )， 1 < 4 位置不變
( 1?**4**?**2**?5 8 ) → ( 1?**2**?**4**?5 8 )， 4 > 2 交換位置
( 1 2?**4**?**5**?8 ) → ( 1 2?**4**?**5**?8 )， 4 < 5 位置不變
第三次外循環（除開已經排序好的最后兩個元素，可以注意到上面的數組其實已經排序完成，但是程序本身并不知道，所以還要進行后續的循環，直到剩余的序列為 1）
(?**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 )
## JavaScript 語言實現
~~~
function bubbleSort(array) {
var length = array.length,
i,
j,
temp;
for (i = length - 1; 0 < i; i--) {
for (j = 0; j < i; j++) {
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
return array;
}
~~~
## 參考文章
* [en.wikipedia.org](http://en.wikipedia.org/wiki/Bubble_sort)
* [維基百科，自由的百科全書](http://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F)
* [Bubble Sort](http://www.sorting-algorithms.com/bubble-sort)
* [經典排序算法 - 冒泡排序Bubble sort](http://www.cnblogs.com/kkun/archive/2011/11/23/2260280.html)
* [冒泡排序](http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.3.1.1.htm)
