Java冒泡排序中array.length - i -1的作用及算法原理解析

冒泡排序的核心工作原理 #

冒泡排序的逻辑很直白：通过反复比较相邻元素，把较大的元素逐步"冒泡"到数组末尾。

• 每一轮只遍历数组的未排序部分，只要发现相邻两个元素顺序不对（前一个比后一个大），就交换它们的位置。
• 每完成一轮遍历，当前未排序部分里的最大元素就会被移到未排序部分的末尾，也就是它最终的排序位置。
• 重复这个过程，直到整个数组完全有序。

举个简单例子：假设数组是[3,1,4,2]

1. 第一轮遍历：比较3和1（交换→[1,3,4,2]），比较3和4（不换），比较4和2（交换→[1,3,2,4]）。此时最大的4已经在末尾，属于已排序部分。
2. 第二轮遍历：只需要处理前3个元素[1,3,2]，比较1和3（不换），比较3和2（交换→[1,2,3,4]）。次大的3移到倒数第二位置。
3. 第三轮遍历：处理前2个元素[1,2]，比较后发现已经有序，遍历结束。

嵌套循环条件array.length - i - 1的作用 #

先看外层循环的i：它代表已经完成排序的元素个数。每执行完一轮外层循环，数组末尾就多一个排好序的最大元素，i的值加1。

内层循环的终止条件array.length - i - 1有两个关键作用：

1. 避免数组越界：内层循环里要访问array[j+1]，如果j的最大值是array.length - 1，j+1就会超出数组下标范围。用array.length - i -1作为j的上限，能保证j+1始终是合法下标。
2. 跳过已排序的末尾元素：因为每轮外层循环后，末尾的i个元素已经是有序的最大值，不需要再对它们进行比较。比如第i轮时，末尾i个元素已经排好，内层循环只需要遍历前array.length - i个元素，而j要和j+1比较，所以上限设为array.length - i -1。

结合你提供的代码来看：

for(int i = 0; i < array.length - 1 ; i++) {
    // 每轮只遍历到未排序部分的倒数第二个元素
    for(int j = 0 ; j < array.length - i - 1 ; j++) {
        if(array[j] > array[j+1]) {
            // 交换相邻逆序元素
            int temp = array[j];
            array[j] = array[j+1];
            array[j+1] = temp;
        }
    }
}

外层循环只需要执行array.length -1次，因为当只剩最后一个元素时，它自然是有序的，不需要再处理。

内容的提问来源于stack exchange，提问作者Thu Ra Lynn Htun