每日算法 — 使用java实现冒泡排序：简单比较排序与提前终止优化

冒泡排序（Bubble Sort）是最经典的比较排序算法之一，其核心思想是通过相邻元素的反复交换，将最大（或最小）的元素逐步”冒泡”到数组的一端。尽管它在实际工程中的使用频率不如快速排序或归并排序，但冒泡排序的教学价值极高：它直观展示了排序的本质——通过比较和交换消除逆序对，同时其优化版本（提前终止标志位）也引入了算法优化的基本思维。

算法原理

冒泡排序的基本流程如下：从数组的第一个元素开始，依次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们。每一轮遍历结束后，当前未排序区间的最大元素会”沉”到正确的位置。重复这个过程，直到整个数组有序。

为了优化性能，可以引入一个布尔标志位 swapped。如果在某一轮遍历中没有发生任何交换，说明数组已经有序，此时可以提前终止排序。这个优化在最优情况下将时间复杂度降为 O(n)。

Java 实现

import java.util.Arrays;

/**
 * 冒泡排序完整实现，包含基础版本与优化版本
 */
public class BubbleSort {

    /**
     * 基础冒泡排序：每轮将当前最大值移动到末尾
     *
     * @param arr 待排序数组
     */
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        // 外层循环控制排序轮数，每轮确定一个元素的最终位置
        for (int i = 0; i < n - 1; i++) {
            // 内层循环进行相邻元素比较与交换
            // 已经排好序的末尾元素无需再比较，所以范围是 0 到 n-1-i
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换相邻逆序元素
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 优化版冒泡排序：引入提前终止机制
     * 当某一轮未发生交换时，说明数组已有序，直接退出
     *
     * @param arr 待排序数组
     */
    public static void bubbleSortOptimized(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]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true; // 标记本轮发生了交换
                }
            }
            // 若本轮无交换，数组已有序，提前终止
            if (!swapped) {
                break;
            }
        }
    }

    /**
     * 进一步优化的冒泡排序：记录最后一次交换的位置
     * 该位置之后的元素已有序，下一轮只需比较到此位置
     *
     * @param arr 待排序数组
     */
    public static void bubbleSortAdvanced(int[] arr) {
        int n = arr.length;
        // 记录每轮最后一次发生交换的位置，该位置之后已有序
        int sortBorder = n - 1;
        while (sortBorder > 0) {
            int lastSwapIndex = 0;
            for (int j = 0; j < sortBorder; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    lastSwapIndex = j; // 更新最后交换位置
                }
            }
            // 缩小下一轮比较范围
            sortBorder = lastSwapIndex;
        }
    }

    public static void main(String[] args) {
        int[] arr1 = {64, 34, 25, 12, 22, 11, 90};
        int[] arr2 = arr1.clone();
        int[] arr3 = arr1.clone();

        System.out.println("原始数组: " + Arrays.toString(arr1));

        bubbleSort(arr1);
        System.out.println("基础排序结果: " + Arrays.toString(arr1));

        bubbleSortOptimized(arr2);
        System.out.println("优化排序结果: " + Arrays.toString(arr2));

        bubbleSortAdvanced(arr3);
        System.out.println("进阶优化结果: " + Arrays.toString(arr3));

        // 测试已有序数组的最优性能
        int[] sorted = {1, 2, 3, 4, 5, 6, 7};
        bubbleSortOptimized(sorted);
        System.out.println("已有序数组通过优化版处理: " + Arrays.toString(sorted));
    }
}

复杂度分析

冒泡排序是稳定排序，因为相等元素的相对位置不会在交换过程中改变。空间复杂度为 O(1)，属于原地排序算法。

适用场景与总结

冒泡排序适用于数据量极小（n < 100）或数据基本有序的场景。在教学中，它是理解排序算法、逆序对、以及算法优化思维的绝佳入门案例。对于大规模数据，应优先选择快速排序、归并排序或堆排序等更高效的算法。