1. 基本概念
1.1 算法原理
冒泡排序就是從序列中的第一個元素開始，依次對相鄰的兩個元素進行比較，如果前一個元素大於後一個元素則交換它們的位置。如果前一個元素小於或等於後一個元素，則不交換它們；這一比較和交換的操作一直持續到最後一個還未排好序的元素為止。
當這樣的一趟操作完成時，序列中最大的未排序元素就被放置到了所有未排序的元素中最後的位置上，它就像水中的石塊一樣沉到了水底。而其它較小的元素則被移動到了序列的前面，就像水中的氣泡冒到了水面一樣。這就是為什麼該算法被叫做冒泡排序的原因。
圖1 冒泡排序的基本原理
圖1展示了冒泡排序的基本原理。假設一個序列中共有 n 個元素，那麼上面的比較和交換過程一共需要進行 n-1 趟：
第一趟需要比較序列中的所有元素，它的效果是將整個序列中最大的元素放置到了序列最後一個位置上；
第二趟只需要比較前面 n-1 個元素，因為前一趟中已經將最大的元素移到了它最終的位置上了。這一趟結束時，整個序列中第二大的元素就被放置到了倒數第二個位置上。
同樣的，第三趟只需要比較前面 n-2 個元素。該趟結束時，序列中第三大的元素就被放到了倒數第三個位置上。
當進行第 i 趟的時候，需要比較的是前面 n-(i-1) 個元素，因為序列中最大的 i-1 個元素已經在前面的 i-1 趟排序中被排好了。注意，比較 n-(i-1) 個元素需要進行 n-i 次比較。
當最終到達第 n-1 趟的時候，只需要比較序列中最前面的兩個數而已。該趟結束時，序列中第二小的數就被放置到了順數第二個位置上。同時，序列中最小的數也被放到了第一個位置上。整個排序過程完成。
從以上對算法原理的講解中，我們首先可以知道冒泡排序是一種交換排序，它需要進行大量的交換操作。其次，因為當兩個元素相等時它們不會被交換，所以相等元素的相對位置在排序前後不會改變，因此冒泡排序又是一種穩定的排序算法。
假設我們有一個序列，它的元素分別為整數48、12、52、36、5，那麼圖2至圖5則詳細地展示了對該序列進行冒泡排序的整個過程。
圖2 [48, 12, 52, 36, 5] 第1趟排序
圖3 [48, 12, 52, 36, 5] 第2趟排序
圖4 [48, 12, 52, 36, 5] 第3趟排序
圖5 [48, 12, 52, 36, 5] 第4趟排序
下面我們用C語言來表達冒泡排序，可以看到代碼非常簡單，主要就是兩層嵌套的循環語句。外層循環控制第1到第 n-1 趟排序，而內層循環則控制每一趟排序中對前面未排好序的元素進行比較和交換。
<code>/*
* Function: bubbleSort1
* Desccription: 冒泡排序第一版，沒有進行任何優化
* param: array 待排序的序列（數組）
* param: n 序列中的元素數量
*/
void bubbleSort1(int array[], int n) {
/* 定義用於交換元素的臨時變量 */
int temp;
/* 外層循環控制第1至第n-1趟排序 */
for(int i = 1; i < n; ++i) {
/* 內層循環用於第i趟時，對前面n-(i-1)個元素進行比較和交換 */
for(int j = 0; j < (n - i); ++j) {
/* 如果前一個元素大於後一個元素，則交換它們 */
if(array[j] > array[j+1]) {
temp = array[j];
array[j] = array[j+1];
array[j+1] = array[j];
}
}
}
}/<code>
1.2 性能分析
我們對這第一版的冒泡排序進行一下性能分析。一共要進行 n-1 趟，且第 i 趟需要比較 n-i 次，所以總共需要比較(n-1) + (n-2) + ... + 1 = n(n-1)/2次。
在最好的情況（序列中的元素已經排好序）下，總共需要交換0次；而在最壞的情況（序列中的元素為逆序時）下，每一次比較都要進行一次交換。因此總的元素移動次數為總的比較次數的3倍，即3n(n-1)/2；那麼平均的元素移動次數為3n(n-1)/4。
因此，這第一版的冒泡排序的時間複雜度為O(n2)；而空間複雜度為O(1)，因為該算法只需要一個額外的變量用於交換元素。
2. 冒泡排序的第一次優化
序列中的元素有可能出現這樣的情況，即經過前面幾趟的排序後整個序列就已經排好序了，那麼後面的那幾趟排序就不需要再執行了。但是我們上面的第一版的冒泡排序即便是在這種情況下，仍然會執行所有的 n-1 趟的排序。即使後面幾趟排序只進行比較而不需交換元素，但是當數據量很大的時候，這依舊會造成整體性能的明顯下降。
因此，我們首先想到的優化方案就是當某一趟排序之後，如果整個序列已排好序了，那麼就立即退出函數。這要怎麼實現呢？其實很簡單，只要在某一趟的排序中沒有進行任何一次的元素交換，那麼此時整個序列就排好序了。
因此，在每一趟排序的開始將一個標記swapped設置為0。在這一趟排序過程中，如果發生了數據交換，那麼就將swapped設置為1。當這一趟排序結束，我們通過檢查該swapped的值就可以知道整個序列是否已經排好序了。
假設我們有一個序列，它的元素分別為整數9、4、6、15、13。那麼圖6至圖7則展示了經本次優化後的冒泡排序的完整執行過程。注意，雖然第一趟排序後整個序列就排好序了，但在第一趟排序中進行了元素交換（swapped被設置為1），算法此時並不知道整個序列已經排好了，所以還要進行第二趟排序。在第二趟排序中，不會進行任何元素交換（swapped最終為0），此時算法才知道整個序列已經是排好序了的。
圖6 [9,4,6,15,13] 第1趟排序
圖7 [9,4,6,15,13] 第2趟排序
<code>/*
* Function: bubbleSort2
* Desccription: 冒泡排序第二版，經過了第一次優化
* param: array 待排序的序列（數組）
* param: n 序列中的元素數量
*/
void bubbleSort2(int array[], int n) {
/*
* temp: 用於交換元素的臨時變量；
* swapped: 標記每一趟中是否發生了元素交換，0表示未交換，1表示交換了。
*/
int temp;
int swapped;
/* 外層循環控制第1至第n-1趟排序 */
for(int i = 1; i < n; ++i) {
/* 每一趟開始時，將swapped重置為0 */
swapped = 0;
/* 內層循環用於第i趟時，對前面n-(i-1)個元素進行比較和交換 */
for(int j = 0; j < (n - i); ++j) {
/* 如果前一個元素大於後一個元素，則交換它們 */
if(array[j] > array[j+1]) {
temp = array[j];
array[j] = array[j+1];
array[j+1] = array[j];
/* 標記發生了元素交換*/
swapped = 1;
}
}
/*
* 每一趟結束後，檢查是否發生了交換；
* 如果沒有發生任何交換，則提前退出整個算法。
*/
if(!swapped) {
return;
}
}
}/<code>
在最好的情況下，第二版冒泡排序只需進行n-1次比較和0次元素移動；在最壞的情況下，還是進行n(n-1)/2次比較和3n(n-1)/2次元素移動。雖然這一版的冒泡排序的時間複雜度依舊是O(n2)，但是和第一版相比肯定性能上更好。
3. 冒泡排序的第二次優化
在我們之前的想法中，當進行第 i 趟排序時，序列中只有最大的 i-1 個元素已經排好序了。因為那時我們認為每一趟僅排好一個元素，即它比較的所有元素中最大的那一個。因此第 i 趟排序的時候，需要對前面 n-(i-1) 個元素進行比較和交換。但其實此時這前 n-(i-1) 個元素中可能最大的那幾個元素已經在它們最終的位置上了，這時第 i 趟實際需要比較的元素個數就可以小於n-(i-1)。
比如有一個序列24、30、12、40、50，那麼第1趟排序之後的結果為24、12、30、40、50。在原來的想法中，第2趟需要比較前面4個數。但此時前4個數中最大的兩個30和40已經在它們最終的位置上了，不需要再對它們進行位置上的調整。因此，第2趟可以只比較前兩個數。
注意這個例子中，雖然在序列的初始狀態中40和50就已經在它們最終的位置上了，但第1趟排序還是需要比較全部的5個數。因為此時沒有任何信息可以將序列的這種特殊狀態告知算法，某一趟是否可以執行比它原本理論上更少的比較次數，需要前一趟排序對序列狀態的瞭解。
在每一趟排序中，我們都用一個變量lastIndex記錄下本趟排序最後一次元素交換中前一個元素的下標。在該下標之後沒有發生交換，說明該下標之後的所有元素都已經排好序了。那麼下一趟排序就只需要對該下標及其之前的元素進行比較而已。這樣下一趟排序需要比較的次數可能比原本需要的次數更少，也就在一定程度上提升了算法的效率。
<code>/*
* Function: bubbleSort3
* Desccription: 冒泡排序第三版，經過了第二次優化
* param: array 待排序的序列（數組）
* param: n 序列中的元素數量
*/
void bubbleSort3(int array[], int n) {
/*
* temp: 用於交換元素的臨時變量；
* swapped: 標記每一趟中是否發生了元素交換，0表示未交換，1表示交換了；
* lastIndex: 記錄每一趟中最後一次交換中前一個元素的下標，它的初值為n-1。
*/
int temp;
int swapped;
int lastIndex = n - 1;
/* 外層循環控制第1至第(n-1)趟排序 */
for(int i = 1; i < n; ++i) {
/* 每一趟開始時，將swapped重置為0 */
swapped = 0;
/* 內層循環用於第i趟時，對前面lastIndex+1個元素進行比較和交換 */
for(int j = 0; j < lastIndex; ++j) {
if(array[j] > array[j+1]) {
/* 交換數據 */
temp = array[j];
array[j] = array[j+1];
array[j+1] = array[j];
/* 標記發生了元素交換 */
swapped = 1;
/* 記錄本次交換中前一個元素的下標 */
lastIndex = j;
}
}
/*
* 每一趟結束後，檢查是否發生了交換；
* 如果沒有發生任何交換，則提前退出整個算法。
*/
if(!swapped) {
return;
}
}
}/<code>
圖8 [24, 30, 12, 40, 50] 第1趟排序
圖9 [24, 30, 12, 40, 50] 第2趟排序
圖10 [24, 30, 12, 40, 50] 第3趟排序
圖8至圖10詳細展示了經過第二次優化後的冒泡排序對[24, 30, 12, 40, 50]這個序列的執行情況。該例子中另一個值得注意的問題是，雖然在第2趟排序後整個序列就已經排好序了，但是第2趟中進行了一次元素交換而導致swapped等於1。因此第2趟後並不會立即退出函數，還要進行第3趟排序。在第3趟中內層循環不會執行而立即退出，因為此時lastIndex等於0，j（此時也等於0）小於lastIndex的條件不滿足。在第3趟最後swapped為0，此時才退出算法。
這個例子的關鍵是要體會到為什麼第2趟排序中只需比較前兩個數而已，而不是前4個數。
（完）
閱讀更多 青石野草 的文章
