C++ 冒泡排序演算法常見錯誤與正確實作

冒泡排序：第二層迴圈起始索引常見錯誤

初學者撰寫冒泡排序時，最常見的錯誤是內層迴圈起始值設定不正確，導致排序結果錯誤或效能低落。

❌ 錯誤寫法：內層從 0 開始

// 錯誤：每次都從頭比較，重複比較已排序元素
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n - 1; j++) {  // 錯誤：j 從 0 開始
        if (arr[j] > arr[j + 1]) {
            swap(arr[j], arr[j + 1]);
        }
    }
}

✅ 正確寫法：內層從 i+1 或 0 到 n-i-1

// 標準冒泡排序：每輪將最大值「冒泡」到末尾
void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {           // 趟數
        for (int j = 0; j < n - 1 - i; j++) {   // 關鍵：n-1-i 避免重複比較
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

🎯 進階優化：提早結束旗標

void optimizedBubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                swapped = true;
            }
        }
        if (!swapped) break; // 本輪無交換，代表已有序
    }
}

🔄 選擇排序寫法（原回答程式碼）

原回答提供的程式碼實際上是選擇排序而非冒泡排序：

// 選擇排序：每輪選出最小值放到前面
void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < arr.length; j++) { // j 從 i+1 開始
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        swap(arr, i, minIdx);
    }
}

兩者差異比較

除錯建議

1. 用小陣列 [3, 1, 2] 手動追蹤索引變化
2. 列印每輪排序後陣列狀態觀察
3. 注意迴圈邊界：i < n-1、j < n-1-i
4. 區分「冒泡」與「選擇」兩種演算法邏輯

掌握排序演算法的迴圈邊界條件，是演算法入門的關鍵基礎。