什么是冒泡排序呢？冒泡排序的英語名是Bubble Sort，是一種最基礎(chǔ)的交換排序。
大家一定都喝過汽水吧，汽水中常常有許多小小的氣泡，往上飄，這是因為組成小氣泡的二氧化碳比水要輕，所以小氣泡才會一點一點的向上浮。而冒泡排序之所以叫冒泡排序，正是因為這種排序算法的每一個元素都可以向小氣泡一樣，根據(jù)自身大小，一點一點向著數(shù)組的一側(cè)移動。具體如何移動呢？我們來看一下例子， 有8個數(shù)組成一個無序數(shù)列：5,8,6,3,9,2,1,7，希望從大到小排序。按照冒泡排序的思想，我們要把相鄰的元素兩兩進行比較，根據(jù)大小交換元素的位置，
利用雙重for循環(huán)語句可以達到冒泡排序的方法 ，過程如下：
第一輪排序：
1、首先讓5和8進行交換，發(fā)現(xiàn)5比8小，因此元素位置不變。
2、接下來讓8和6比較，發(fā)現(xiàn)8比6大，所以要交換8和6的位置。
![8和6交換位子]
3、繼續(xù)讓8和3比較，發(fā)現(xiàn)8比3要大，所以8和3 交換位置。
4、繼續(xù)讓8和9進行比較，發(fā)現(xiàn)8比9小，不用交換
5、9和2進行比較，發(fā)現(xiàn)9比2大，進行交換
6、繼續(xù)讓9和1進行比較，發(fā)現(xiàn)9比1大，所以交換9和1的位置。
7、最后，讓9和7交換位置，這樣一來，元素9作為數(shù)列的最大元素，就已經(jīng)排序好了。
下面我們來進行第二輪排序：
1、首先讓5和6比較，發(fā)現(xiàn)5比6小，位置不變
2、接下來讓6和3比較，發(fā)現(xiàn)6比3大，交換位置
3、接下來讓6和8比較，6比8小，位置不變
4、8和2比較。8比2大，交換位置
5、接下來讓8和1比較，8比1大，因此交換位置
6、繼續(xù)讓8和7比較，發(fā)現(xiàn)8比7大，交換位置
接著第三輪——>第八輪
到此為止，所有的元素都是有序的了，這就是冒泡排序的整體思路。
原始的冒泡排序是穩(wěn)定的，由于該排序算法的每一輪都要遍歷一遍所有的元素，輪轉(zhuǎn)的次數(shù)和元素數(shù)量相當，所以時間復(fù)雜度為O(N^2)。
下面用C語言描述：
#include<stdio.h>
#include<stdlib.h>
void BubbleSort(int a[], int len)
{
int i, j, temp;
for (j = 0; j < len - 1; j++)
{
for (i = 0; i < len - 1 - j; i++)
if (a[i] > a[i + 1])
{
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}
}
int main()
{
int arr[] = { 5, 8, 6, 3, 9, 2, 1, 7 };
int len = sizeof(arr) / sizeof(arr[0]);
int i = 0;
printf("排序前：");
for (i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
BubbleSort(arr, len);
printf("排序后：");
for (i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
system("pause");
return 0;
}
這個代碼很簡單，使用雙循環(huán)的方式進行排序。外部的循環(huán)控制所有回合，內(nèi)部循環(huán)代表每一輪的冒泡處理，先進行元素比較，再進行元素交換。那么這個代碼該怎么進行優(yōu)化呢？？我們現(xiàn)在來回顧一下之前的描述細節(jié)，仍然以 5,8,6,3,9,2,1,7 為例，當排序伏安法分別執(zhí)行到第六、第七、第八輪的時候，數(shù)列的狀態(tài)其實已經(jīng)變?yōu)橛行虻牧恕?/p>
