✎ 冒泡排序介紹

冒泡排序(Bubble Sort)，又被稱為氣泡排序或泡沫排序。

它是一種較簡單的排序算法。它會遍歷若干次要排序的數列，每次遍歷時，它都會從前往後依次的比較相鄰兩個數的大小；如果前者比後者大，則交換它們的位置。這樣，一次遍歷之後，最大的元素就在數列的末尾！ 採用相同的方法再次遍歷時，第二大的元素就被排列在最大元素之前。重複此操作，直到整個數列都有序為止！

✎ 冒泡排序圖文說明

☀ 冒泡排序C實現一

voidbubble_sort1(inta[],int n)

{

int i,j;

for(i=n-1; i>0; i--)

{

// 將a[0...i]中最大的數據放在末尾for(j=0; j

{

if(a[j] > a[j+1])

swap(a[j], a[j+1]);

}

}

}

————————————

下面以數列{20,40,30,10,60,50}為例，演示它的冒泡排序過程(如下圖)。

我們先分析第1趟排序

當i=5,j=0時，a[0]<a[1]。此時，不做任何處理！

當i=5,j=1時，a[1]>a[2]。此時，交換a[1]和a[2]的值；交換之後，a[1]=30，a[2]=40。

當i=5,j=2時，a[2]>a[3]。此時，交換a[2]和a[3]的值；交換之後，a[2]=10，a[3]=40。

當i=5,j=3時，a[3]<a[4]。此時，不做任何處理！

當i=5,j=4時，a[4]>a[5]。此時，交換a[4]和a[5]的值；交換之後，a[4]=50，a[3]=60。

於是，第1趟排序完之後，數列{20,40,30,10,60,50}變成了{20,30,10,40,50,60}。此時，數列末尾的值最大。

根據這種方法：

第2趟排序完之後，數列中a[5...6]是有序的。

第3趟排序完之後，數列中a[4...6]是有序的。

第4趟排序完之後，數列中a[3...6]是有序的。

第5趟排序完之後，數列中a[1...6]是有序的。

第5趟排序之後，整個數列也就是有序的了。

☀ 冒泡排序C實現二

觀察上面冒泡排序的流程圖，第3趟排序之後，數據已經是有序的了；第4趟和第5趟並沒有進行數據交換。

下面我們對冒泡排序進行優化，使它效率更高一些：添加一個標記，如果一趟遍歷中發生了交換，則標記為true，否則為false。如果某一趟沒有發生交換，說明排序已經完成！

voidbubble_sort2(inta[],int n)

{

int i,j;

intflag;// 標記for(i=n-1; i>0; i--)

{

flag =0;// 初始化標記為0

// 將a[0...i]中最大的數據放在末尾for(j=0; j

{

if(a[j] > a[j+1])

{

swap(a[j], a[j+1]);

flag =1;// 若發生交換，則設標記為1 }

}

if(flag==0)

break;// 若沒發生交換，則說明數列已有序。 }

}

✎ 冒泡排序的時間複雜度和穩定性

۞ 冒泡排序時間複雜度

冒泡排序的時間複雜度是O(N2)。

假設被排序的數列中有N個數。遍歷一趟的時間複雜度是O(N)，需要遍歷多少次呢？N-1次！因此，冒泡排序的時間複雜度是O(N2)。

۞ 冒泡排序穩定性

冒泡排序是穩定的算法，它滿足穩定算法的定義。

算法穩定性 -- 假設在數列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；並且排序之後，a[i]仍然在a[j]前面。則這個排序算法是穩定的！

「我是一名從事了10年開發在退休邊緣垂死掙扎的高齡程式設計師，最近我花了一些時間整理了一個完整的學習C語言、C++的路線，項目源碼和工具。對於想學習C/C++的小夥伴而言，學習的氛圍和志同道合的夥伴很重要，筆者推薦一個C語言/C++編程愛好者的聚集地>>>私信我【編程學習】即可！

歡迎初學和進階中的小夥伴。希望你也能憑自己的努力，成為下一個優秀的程式設計師。工作需要、感興趣、為了入行、轉行需要學習C/C++的夥伴可以一起學習！」

關注我，帶你遨遊代碼世界！

最後分享一張C/C++編程學習路線圖給愛學習小夥伴們~