氣泡排序

Harshit Jindal 2023年1月30日 2021年2月7日
  1. 氣泡排序演算法
  2. 氣泡排序演算法示例
  3. 氣泡排序演算法的實現
  4. 氣泡排序演算法的複雜度
氣泡排序

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

氣泡排序演算法

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

  • 從前兩個元素的對子(A[0]A[1])開始,比較它們的值,如果它們的順序不對,就交換它們。對下一對元素(A[1]A[2])做同樣的操作,並對陣列的其餘部分做類似的移動。最小/最大的元素在這一步之後的最後一個位置。
  • 對剩餘的迭代重複上述步驟 (n-2) 次。每次陣列大小減一,因為最後一個元素已經被排序。本次迭代中最小/最大的元素移動到最右邊的位置。

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

氣泡排序演算法示例

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

  • 第一次執行:
(** 5 3 ** 4 2 1) (** 3 5 ** 4 2 1) (交換 3 <5)
(3 ** 5 4 ** 2 1) (3 ** 4 5 ** 2 1) (交換 4 <5)
(3 4 ** 5 2 ** 1) (3 4 ** 2 5 ** 1) (交換 2 <5)
(3 4 2 ** 5 1 **) (3 4 2 ** 1 5 **) (交換 1 <5)
  • 第二次執行:
(** 3 4 ** 2 1 5) (** 3 4 ** 2 1 5)
(3 ** 4 2 ** 1 5) (3 ** 2 4 ** 1 5) (交換 2 <4)
(3 2 ** 4 1 ** 5) (3 2 ** 1 4 ** 5) (交換 1 <4)
  • 第三次執行:
(** 3 2 ** 1 4 5) (** 2 3 ** 1 4 5) (交換 2 <3)
(2 ** 3 1 ** 4 5) (2 ** 1 3 ** 4 5) (交換<1 <3)
  • 第四次執行:
(** 2 1 ** 3 4 5) (** 1 2 ** 3 4 5) (交換 1 <2)

第四次執行後,我們得到排序陣列 - (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(n2)。

  • 最壞情況

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

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

  • 最佳情況

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

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

空間複雜度

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

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相關文章 - Sort Algorithm