如何优化Java实现的冒泡排序 减少循环次数提升运行效率

原代码存在的冗余问题 #

原实现的冒泡排序未利用冒泡过程的有序性特征，存在两处明显的可优化点：

• 每轮冒泡结束后，尾部已有序的元素不会再发生位置变化，原代码仍会对这部分元素做重复比较
• 若数组中途已经完全有序，原代码仍会走完所有预设的轮次，产生大量无效循环

核心优化思路 #

我们可以通过两个小改动大幅减少循环次数，将最好场景下的时间复杂度从O(n²)降至O(n)：

• 增加有序边界判断：每轮遍历只到上一轮最后一次发生交换的位置，该位置之后的元素已经有序，无需再比较
• 增加提前终止标记：若某一轮遍历全程没有发生任何交换，说明整个数组已经有序，直接终止排序流程

优化后的核心代码 #

只需要替换原有的bubbleSort方法即可，其余代码无需改动：

public static void bubbleSort(int tempArray[]) {
    // 记录最后一次交换的位置，初始值为数组末尾
    int lastSwapIndex = tempArray.length - 1;
    // 本轮遍历的右边界，边界右侧均为已排序元素
    int rightBoundary = lastSwapIndex;
    // 轮次计数
    for (int pass = 1; pass < tempArray.length; pass++) {
        System.out.println(pass);
        // 标记本轮是否发生过交换
        boolean hasSwap = false;
        // 内层循环仅遍历到右边界即可
        for (int element = 0; element < rightBoundary; element++) {
            if (tempArray [element] > tempArray [element + 1]) {
                swap (tempArray, element, element + 1);
                hasSwap = true;
                // 更新最后一次交换的位置
                lastSwapIndex = element;
            }
        }
        // 本轮无交换，数组已完全有序，直接退出
        if (!hasSwap) {
            break;
        }
        // 更新下一轮的右边界
        rightBoundary = lastSwapIndex;
    }
}

优化效果验证 #

• 针对完全有序的数组：仅需1轮遍历即可终止排序，共做n-1次比较，无交换操作
• 针对部分有序的数组：右边界会快速收缩，大幅减少无效比较次数
• 最坏场景（完全逆序）下的效率和原实现一致，不会产生额外性能损耗

内容的提问来源于stack exchange，提问作者Joey Rudd Student