系列文章目錄

?第一篇：【排序算法】①直接插入排序-CSDN博客

第二篇：【排序算法】②希爾排序-CSDN博客

第三篇：【排序算法】③直接選擇排序-CSDN博客

第四篇：【排序算法】④堆排序-CSDN博客

第五篇：【排序算法】⑤冒泡排序-CSDN博客

第六篇：【排序算法】⑥快速排序：Hoare、挖坑法、前后指針法-CSDN博客

第七篇：【排序算法】⑦歸并排序-CSDN博客

---

---

前言

冒泡排序屬于交換排序的一種。交換排序基本思想：所謂交換，就是按序列中兩個數據碼值的比較結果來決定是否對換這兩個數據在序列中的位置。

交換排序的特點是：將碼值大的向尾部移動，碼值小的往前移動

冒泡排序實現簡單，主要是為后續同屬于交換排序的快排做鋪墊，故本文篇幅較短。

---

一、冒泡排序是什么？

冒泡排序的基本思想

1. 比較相鄰的元素：首元素設從i=0開始，依次比較相鄰的兩個元素（j=i+1）。如果第一個比第二個大（升序排序），就交換它們。

2.?然后i不變，j++，循環直到 j 到達數組末尾，此時最后一個數據一定是該數據集最大的。

3. i++，重復上述步驟，直到遍歷完整個數組。

核心思想：重復遍歷數組，比較相鄰元素，如果順序錯誤就交換它們

排序過程：每輪遍歷會將當前最大的元素"冒泡"到正確位置，類似水中的氣泡上浮，因此得名。

二、冒泡排序圖解

設數組為int a[ ]={5，3，8，4，2}，兩層循環，外層循環控制 i=0，內存控制 j=i+1，各自的循環結束時++，結束條件為到達數組末尾<n;

三、實現代碼

以升序為例，降序同理。

//冒泡排序
void BubbleSort(int* a, int n)
{if (!a)return;for (int i = 0; i < n; ++i){int Change = 1;for (int j = i + 1; j < n; ++j){if (a[i] > a[j]){swap(&a[i], &a[j]);Change = 0;}}//如果Change的值未變,則說明數組后續數據都有序if (Change)break;}
}void swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}

break優化解釋：

如果在i=某值的一輪比較中，Change的值都未發生改變（即內循環沒有發生交換），說明后續數據都大于或等于a[i]且呈現遞增趨勢為有序狀態，故此時可以跳出循環，提前結束排序。

四、分析冒泡排序

冒泡排序的特性總結：
1. 冒泡排序是一種較容易理解的排序；
2. 時間復雜度：O(N^2)，（若加上break優化，則較不優化平均快上3倍）；
3. 空間復雜度：O(1)
4. 穩定性：穩定

---

總結

本文是【排序算法】系類第五篇，主要介紹什么是冒泡排序，以及如何實現冒泡排序，最后分析冒泡排序特性。

冒泡排序較為簡單，但它是為同為交換排序的“快速排序”做鋪墊，快速排序是當今實際代碼中最常使用的排序，也是本系列的重點所在。