跳转至

冒泡排序

本頁面將簡要介紹冒泡排序。

定義

冒泡排序（英語：Bubble sort）是一種簡單的排序算法。由於在算法的執行過程中，較小的元素像是氣泡般慢慢「浮」到數列的頂端，故叫做冒泡排序。

過程

它的工作原理是每次檢查相鄰兩個元素，如果前面的元素與後面的元素滿足給定的排序條件，就將相鄰兩個元素交換。當沒有相鄰的元素需要交換時，排序就完成了。

經過 \(i\) 次掃描後，數列的末尾 \(i\) 項必然是最大的 \(i\) 項，因此冒泡排序最多需要掃描 \(n-1\) 遍數組就能完成排序。

性質

穩定性

冒泡排序是一種穩定的排序算法。

時間複雜度

在序列完全有序時，冒泡排序只需遍歷一遍數組，不用執行任何交換操作，時間複雜度為 \(O(n)\)。

在最壞情況下，冒泡排序要執行 \(\frac{(n-1)n}{2}\) 次交換操作，時間複雜度為 \(O(n^2)\)。

冒泡排序的平均時間複雜度為 \(O(n^2)\)。

代碼實現

偽代碼

\[ \begin{array}{ll} 1 & \textbf{Input. } \text{An array } A \text{ consisting of }n\text{ elements.} \\ 2 & \textbf{Output. } A\text{ will be sorted in nondecreasing order stably.} \\ 3 & \textbf{Method. } \\ 4 & flag\gets True\\ 5 & \textbf{while }flag\\ 6 & \qquad flag\gets False\\ 7 & \qquad\textbf{for }i\gets1\textbf{ to }n-1\\ 8 & \qquad\qquad\textbf{if }A[i]>A[i + 1]\\ 9 & \qquad\qquad\qquad flag\gets True\\ 10 & \qquad\qquad\qquad \text{Swap } A[i]\text{ and }A[i + 1] \end{array} \]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// 假設數組的大小是 n + 1，冒泡排序從數組下標 1 開始
void bubble_sort(int *a, int n) {
  bool flag = true;
  while (flag) {
    flag = false;
    for (int i = 1; i < n; ++i) {
      if (a[i] > a[i + 1]) {
        flag = true;
        int t = a[i];
        a[i] = a[i + 1];
        a[i + 1] = t;
      }
    }
  }
}

1
2
3
4
5
6
7
8
def bubble_sort(a, n):
    flag = True
    while flag:
        flag = False
        for i in range(1, n):
            if a[i] > a[i + 1]:
                flag = True
                a[i], a[i + 1] = a[i + 1], a[i]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// 假設數組的大小是 n + 1，冒泡排序從數組下標 1 開始
static void bubble_sort(int[] a, int n) {
    boolean flag = true;
    while (flag) {
        flag = false;
        for (int i = 1; i < n; i++) {
            if (a[i] > a[i + 1]) {
                flag = true;
                int t = a[i];
                a[i] = a[i + 1];
                a[i + 1] = t;
            }
        }
    }
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用