氣泡排序

1. 氣泡排序演算法
2. 氣泡排序演算法示例
3. 氣泡排序演算法的實現
4. 氣泡排序演算法的複雜度

氣泡排序是一種簡單的排序演算法。它的工作原理是對相鄰元素進行反覆比較，如果它們的順序不對，則進行交換。反覆比較後，將最小/最大的元素向陣列最後冒泡，因此這種演算法被命名為氣泡排序。雖然效率不高，但它仍然代表了排序演算法的基礎。

氣泡排序演算法

假設我們有一個未排序的陣列 A[]，包含 n 個元素。

上述演算法中的第 1 步也稱為執行。要對一個大小為 n 的陣列進行排序，需要進行 n-1 次的執行。

氣泡排序演算法示例

假設我們有陣列：(5,3,4,2,1). 我們將使用氣泡排序演算法對其進行排序。

• 第一次執行：

• 第二次執行：

• 第三次執行：

• 第四次執行：

第四次執行後，我們得到排序陣列 - (1 2 3 4 5)。

氣泡排序演算法的實現

#include <iostream>

using namespace std;
void bubble_sort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
      }
    }
  }
}
int main() {
  int n = 5;
  int arr[5] = {5, 3, 4, 2, 1};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  bubble_sort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

氣泡排序演算法的複雜度

時間複雜度

• 平均情況

平均來說，在氣泡排序的第 i 次執行中，會進行 n-i 次比較。因此，如果有 n 個通道，那麼平均的時間複雜度可以用以下方式給出

(n-1) + (n-2) + (n-3) ..... + 1 = n*(n-1)/2

因此，時間複雜度為 O(n²)。

• 最壞情況

最壞的情況發生在陣列被反向排序的時候，並且必須執行最大數量的比較和交換。

最壞的情況下時間複雜度是 O(n²)。

• 最佳情況

最好的情況發生在陣列已經被排序的時候，那麼只需要進行 N 次比較。

最佳情況下的時間複雜度為 O(n)。

空間複雜度

這個演算法的空間複雜度是 O(n)，因為除了一個臨時變數外，不需要額外的記憶體。