Java中的冒泡排序算法详解

1. 算法简介

冒泡排序是最直观的排序算法之一，核心思想很简单：不断比较相邻元素，如果顺序错误就交换位置，直到整个数组有序。

小元素会像气泡一样逐渐"浮"到数组顶端，这也是算法名称的由来。由于所有操作都在原数组上进行，它属于原地排序算法。

✅ 稳定排序特性：当两个元素值相等时，它们的相对位置不会改变，这使它成为稳定的排序算法。

2. 算法原理

假设我们要对数组 [4, 2, 1, 6, 3, 5] 进行升序排序，具体步骤如下：

第一轮遍历

比较4和2 → 交换 → [2, 4, 1, 6, 3, 5]
比较4和1 → 交换 → [2, 1, 4, 6, 3, 5]
比较4和6 → 不交换 → [2, 1, 4, 6, 3, 5]
比较6和3 → 交换 → [2, 1, 4, 3, 6, 5]
比较6和5 → 交换 → [2, 1, 4, 3, 5, 6]

⚠️ 关键观察：每轮遍历都会将当前最大元素"冒泡"到正确位置

后续遍历

第二轮：忽略已排序的末尾元素，处理前5个元素
第三轮：处理前4个元素
依此类推，直到所有元素有序

对于长度为n的数组，最多需要 n-1轮 遍历。

3. Java实现

基础实现（Java 8风格）

void bubbleSort(Integer[] arr) {
    int n = arr.length;
    IntStream.range(0, n - 1)
        .flatMap(i -> IntStream.range(1, n - i))
        .forEach(j -> {
            if (arr[j - 1] > arr[j]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
        });
}

单元测试验证

@Test
void whenSortedWithBubbleSort_thenGetSortedArray() {
    Integer[] array = { 2, 1, 4, 6, 3, 5 };
    Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 };
    BubbleSort bubbleSort = new BubbleSort();
    bubbleSort.bubbleSort(array);
    
    assertArrayEquals(array, sortedArray);
}

4. 复杂度分析与优化

时间复杂度

最坏/平均情况：O(n²) - 数组逆序时
最佳情况：O(n) - 数组已有序时

空间复杂度

✅ O(1) - 原地排序，无需额外空间

优化方案

⚠️ 常见坑：基础实现即使数组已有序仍会执行完整遍历

优化思路：如果在某轮遍历中没有发生交换，说明数组已有序，可提前终止。

public void optimizedBubbleSort(Integer[] arr) {
    int i = 0, n = arr.length;
    boolean swapNeeded = true;
    while (i < n - 1 && swapNeeded) {
        swapNeeded = false;
        for (int j = 1; j < n - i; j++) {
            if (arr[j - 1] > arr[j]) {
                // 交换元素
                int temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
                swapNeeded = true;
            }
        }
        if(!swapNeeded) {
            break; // 无交换时提前退出
        }
        i++;
    }
}

优化版测试

@Test
void givenIntegerArray_whenSortedWithOptimizedBubbleSort_thenGetSortedArray() {
    Integer[] array = { 2, 1, 4, 6, 3, 5 };
    Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 };
    BubbleSort bubbleSort = new BubbleSort();
    bubbleSort.optimizedBubbleSort(array);
 
    assertArrayEquals(array, sortedArray);
}

5. 总结

冒泡排序的核心特点：

特性	说明
排序方式	原地排序
稳定性	稳定排序
时间复杂度	最佳O(n)，平均/最坏O(n²)
空间复杂度	O(1)

💡 适用场景：

计算机图形学中检测微小排序错误（如几乎有序的数组）
数据量极小且实现简单的场景
教学演示排序算法原理

虽然效率不高，但它的简单性和稳定性使其在特定场景仍有价值。完整实现代码可参考 GitHub仓库。

Persistence

REST

Security