Java 常见排序算法实现与解析

冒泡排序

冒泡排序是最基础的排序算法之一，通过重复遍历数组，比较相邻元素并交换位置来实现排序。虽然效率不高，但逻辑简单，适合理解排序原理。

public class BubbleSort {
    public static int[] bubbleSort(int[] array) {
        if (array == null) {
            return null;
        }

        for (int i = 0; i < array.length - 1; i++) {
            // 优化：如果本轮没有发生交换，说明已经有序，可提前结束
            boolean swapped = false;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    // 使用临时变量交换，避免整数溢出风险
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }

        return array;
    }
}

注意这里我稍微调整了循环边界和交换逻辑。原代码中的算术交换（加减法）在极端情况下可能导致整数溢出，实际开发中建议使用临时变量。另外增加了 swapped 标记，当某一轮遍历未发生任何交换时，说明数组已有序，可以直接退出，提升性能。

插入排序

插入排序的思路类似于整理扑克牌。它将数组分为'已排序'和'未排序'两部分，每次从未排序部分取出一个元素，插入到已排序部分的合适位置。

public class InsertSort {
    public static int[] insertSort(int[] array) {
        if (array == null || array.length <= 1) {
            return array;
        }

        for (int i = 1; i < array.length; i++) {
            int key = array[i];
            int j = i - 1;

            // 将比 key 大的元素向后移动一位
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }

        return array;
    }
}

这段代码补全了原本截断的逻辑。核心在于内层的 while 循环，它负责找到插入点并将大元素后移。插入排序在处理小规模或部分有序的数据时表现优于冒泡排序，且是稳定的排序算法。

小结

这两种算法都属于 $O(n^2)$ 的时间复杂度，适合数据量较小的场景。在实际工程中，面对大规模数据通常会选择快速排序、归并排序或堆排序。理解这些基础算法有助于深入掌握更复杂的结构设计与优化思路。