（1）冒泡排序 (Bubble Sort)

算法原理

冒泡排序（Bubble Sort，臺(tái)灣譯為：泡沫排序或氣泡排序）是一種簡單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

冒泡排序算法的流程如下：

1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
3. 針對所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
4. 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

由于它的簡潔，冒泡排序通常被用來對于程序設(shè)計(jì)入門的學(xué)生介紹算法的概念。

圖片來自維基百科

實(shí)例分析

以數(shù)組 arr = [5, 1, 4, 2, 8] 為例說明，加粗的數(shù)字表示每次循環(huán)要比較的兩個(gè)數(shù)字：

第一次外循環(huán)

(?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 位置不變

第二次外循環(huán)（除開最后一個(gè)元素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 位置不變

第三次外循環(huán)（除開已經(jīng)排序好的最后兩個(gè)元素，可以注意到上面的數(shù)組其實(shí)已經(jīng)排序完成，但是程序本身并不知道，所以還要進(jìn)行后續(xù)的循環(huán)，直到剩余的序列為 1）

(?1?2?4 5 8 ) → (?1?2?4 5 8 )
( 1?2?4?5 8 ) → ( 1?2?4?5 8 )

第四次外循環(huán)（最后一次）
(?1?2?4 5 8 ) → (?1?2?4 5 8 )

JavaScript 語言實(shí)現(xiàn)

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
• 維基百科，自由的百科全書
• Bubble Sort
• 經(jīng)典排序算法 - 冒泡排序Bubble sort
• 冒泡排序