排序算法面試必備：冒泡排序與選擇排序的原理、代碼實現與穩定性對比

排序算法面試必備：冒泡排序與選擇排序的原理、代碼實現與穩定性對比

冒泡排序與選擇排序是最基礎的 O(n²) 排序，理解其差異是演算法入門關鍵。

冒泡排序

核心思想：相鄰元素兩兩比較，大的「冒泡」到右側。每輪將當前最大值移至未排序區末尾。

特性：

• 穩定排序：相等元素不交換，相對順序不變。
• 最佳情況 O(n)：已有序時，一輪無交換即可提前結束（需優化標誌位）。
• 原地排序：空間 O(1)。

優化代碼 (C)：

void bubble_sort(int a[], int n) {
    for (int i = 0; i < n-1; i++) {
        int swapped = 0;
        for (int j = 0; j < n-1-i; j++) {
            if (a[j] > a[j+1]) {
                int t = a[j]; a[j] = a[j+1]; a[j+1] = t;
                swapped = 1;
            }
        }
        if (!swapped) break; // 提前終止
    }
}

選擇排序

核心思想：每輪在未排序區找最小值，與區首元素交換。

特性：

• 不穩定：如 [5, 5, 3] 首輪將第一個 5 與 3 交換，導致相等元素順序顛倒。
• 交換次數固定 O(n)：無論數據分佈，僅 n-1 次交換，適合寫入代價高的存儲介質。
• 無最佳情況優化：始終需完整掃描未排序區。

代碼 (C)：

void select_sort(int a[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min = i;
        for (int j = i+1; j < n; j++)
            if (a[j] < a[min]) min = j;
        if (min != i) {
            int t = a[i]; a[i] = a[min]; a[min] = t;
        }
    }
}

對比總結

實際工程中，小數據量首選 std::sort (Introsort, O(n log n))，僅教學或極受限環境才手寫 O(n²) 排序。