（1）冒泡排序 (Bubble Sort)

算法原理

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

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

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

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

圖片來(lái)自維基百科

實(shí)例分析

以數(shù)組 arr = [5, 1, 4, 2, 8] 為例說(shuō)明，加粗的數(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)（除開(kāi)最后一個(gè)元素8，對(duì)剩余的序列）

(?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)（除開(kāi)已經(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 語(yǔ)言實(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
• 冒泡排序