您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

深入淺出理解排序算法：冒泡排序原理與實現

編輯：C++ 入門

冒泡排序：從入門到精通

冒泡排序是最基礎的排序算法之一，雖然時間複雜度為 O(n²)，但在教學與小規模數據排序中極具價值。本文將詳細解析其核心思想、代碼實現與優化方向。

核心思想

冒泡排序的基本邏輯是：重複遍歷待排序序列，比較相鄰元素，若順序錯誤則交換。每一輪遍歷都會將當前未排序部分的最大（或最小）元素「冒泡」到正確位置。對於長度為 n 的數組，需進行 n-1 輪遍歷，第 i 輪需比較 n-i 次。

關鍵特性

時間效率：最壞與平均情況 O(n²)，最好情況（已有序）可優化至 O(n)
空間效率：原地排序，僅需 O(1) 輔助空間
穩定性：穩定排序，相等元素相對順序不變

C++ 標準實現

#include <iostream>
using namespace std;

void Swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

void BubbleSort(int array[], int len) {
    for (int i = 0; i < len - 1; ++i) {
        for (int j = len - 1; j > i; --j) {
            if (array[j - 1] > array[j]) {
                Swap(array[j], array[j - 1]);
            }
        }
    }
}

int main() {
    int a[] = {5, 4, 9, 8, 7, 6, 0, 1, 3, 2};
    int len = sizeof(a) / sizeof(a[0]);
    
    BubbleSort(a, len);
    
    for (int i = 0; i < len; ++i) {
        cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}

優化方向

引入標誌位 swapped，若某輪遍歷未發生交換，說明數組已有序，可提前終止：

void OptimizedBubbleSort(int arr[], int n) {
    bool swapped;
    for (int i = 0; i < n - 1; ++i) {
        swapped = false;
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // 已有序，提前退出
    }
}