逐行代码解析：冒泡排序的条件设置

让我们深入解析冒泡排序中关键的条件设置，特别是内层循环的 j < n - i - 1 条件。我会用 Java 代码为例进行解析，Python 的逻辑完全相同。

完整代码回顾（Java版本）

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;        // 1. 获取数组长度
        boolean swapped;           // 2. 优化标志位

        for (int i = 0; i < n - 1; i++) {  // 3. 外层循环：控制排序轮数
            swapped = false;      // 4. 每轮开始重置标志位

            for (int j = 0; j < n - i - 1; j++) {  // 5. 内层循环：核心比较逻辑
                if (arr[j] > arr[j + 1]) {  // 6. 比较相邻元素
                    // 7. 交换元素
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;  // 8. 标记发生了交换
                }
            }

            if (!swapped) break;    // 9. 优化：无交换则提前终止
        }
    }
    // ... 其他方法 ...
}

---

关键条件解析

1. 外层循环：for (int i = 0; i < n - 1; i++)

• 作用：控制排序的轮数
• 为什么是 n-1？
  • 每轮外层循环会将当前最大元素"冒泡"到正确位置
  • 对于长度为 n 的数组，最多需要 n-1 轮排序
  • 示例：5个元素最多需要4轮排序

    初始: [5, 4, 3, 2, 1]
    第1轮: [4, 3, 2, 1, 5]  (最大元素5到位)
    第2轮: [3, 2, 1, 4, 5]  (次大元素4到位)
    第3轮: [2, 1, 3, 4, 5]  (元素3到位)
    第4轮: [1, 2, 3, 4, 5]  (元素2到位)

2. 内层循环：for (int j = 0; j < n - i - 1; j++)

这是最关键的条件，让我们详细分解：

• j 的作用：遍历数组，比较相邻元素 arr[j] 和 arr[j+1]
• 为什么是 n - i - 1？
  • n：数组总长度
  • i：当前已完成排序的轮数（即已排序好的元素个数）
  • -1：因为比较的是 j 和 j+1，避免数组越界

逐步解析：

1. 每轮外层循环后，数组末尾的 i 个元素已经有序

   • 第1轮后：最后1个元素是最大值
   • 第2轮后：最后2个元素已排序
   • 第3轮后：最后3个元素已排序
   • ...

2. 因此，每轮内层循环只需要处理未排序部分

   • 未排序部分长度 = n - i
   • 需要比较的索引范围：0 到 n - i - 2
   • 因为要比较 j 和 j+1，所以 j 的最大值是 n - i - 2
   • 循环条件 j < n - i - 1 确保了这一点

可视化示例（数组长度 n=5）：

轮数(i)	未排序部分	内层循环范围(j)	比较对
0	[0,1,2,3,4]	j=0,1,2,3	(0,1),(1,2),(2,3),(3,4)
1	[0,1,2,3]	j=0,1,2	(0,1),(1,2),(2,3)
2	[0,1,2]	j=0,1	(0,1),(1,2)
3	[0,1]	j=0	(0,1)

• 第0轮：n - i - 1 = 5 - 0 - 1 = 4 → j 从0到3
• 第1轮：n - i - 1 = 5 - 1 - 1 = 3 → j 从0到2
• 第2轮：n - i - 1 = 5 - 2 - 1 = 2 → j 从0到1
• 第3轮：n - i - 1 = 5 - 3 - 1 = 1 → j 从0到0

3. 优化条件：if (!swapped) break;

• 作用：检测数组是否已经有序
• 为什么有效？
  • 如果一轮内层循环中没有发生任何交换，说明数组已经有序
  • 无需继续后续轮次，直接终止排序
• 示例：

  初始: [1, 2, 3, 4, 5]
  第1轮: 比较所有相邻元素，无交换 → swapped=false → 直接终止

---

完整执行流程示例

以数组 [5, 1, 4, 2, 8] 为例：

初始状态: [5, 1, 4, 2, 8]

第1轮 (i=0):

• 未排序部分: [5, 1, 4, 2, 8] (全部)
• 内层循环: j 从0到3 (n-i-1=5-0-1=4)
  • j=0: 比较(5,1) → 交换 → [1, 5, 4, 2, 8]
  • j=1: 比较(5,4) → 交换 → [1, 4, 5, 2, 8]
  • j=2: 比较(5,2) → 交换 → [1, 4, 2, 5, 8]
  • j=3: 比较(5,8) → 不交换
• 结果: [1, 4, 2, 5, 8] (最大元素8到位)
• swapped=true (发生了交换)

第2轮 (i=1):

• 未排序部分: [1, 4, 2, 5] (前4个)
• 内层循环: j 从0到2 (n-i-1=5-1-1=3)
  • j=0: 比较(1,4) → 不交换
  • j=1: 比较(4,2) → 交换 → [1, 2, 4, 5, 8]
  • j=2: 比较(4,5) → 不交换
• 结果: [1, 2, 4, 5, 8] (次大元素5到位)
• swapped=true

第3轮 (i=2):

• 未排序部分: [1, 2, 4] (前3个)
• 内层循环: j 从0到1 (n-i-1=5-2-1=2)
  • j=0: 比较(1,2) → 不交换
  • j=1: 比较(2,4) → 不交换
• 结果: [1, 2, 4, 5, 8] (无变化)
• swapped=false → 终止排序

最终结果: [1, 2, 4, 5, 8]

---

关键点总结

1. 内层循环条件 j < n - i - 1 的核心逻辑：

   • n - i：当前未排序部分的长度
   • -1：因为要访问 j+1，避免数组越界
   • 确保每轮只处理未排序部分，且不会越界

2. 为什么这个条件高效：

   • 避免重复比较已排序好的元素
   • 每轮减少比较次数（从 n-1 次递减到1次）
   • 配合 swapped 标志实现提前终止

3. 边界情况处理：

   • 空数组或单元素数组：外层循环 i < n-1 直接不执行
   • 已排序数组：第一轮内层循环后 swapped=false，立即终止

这种条件设置是冒泡排序的标准实现，既保证了正确性，又通过减少不必要的比较进行了优化。理解这个条件的关键在于认识到每轮外层循环后，数组末尾的元素已经有序，无需再参与比较。