排序算法精讲：冒泡排序原理、代码实现与优化分析

排序算法精讲：冒泡排序

面试高频考点，手写排序算法是基本功。本文以冒泡排序为例，拆解核心思想、逐轮演示、代码实现、边界细节与优化方向。

算法思想

对长度为 n 的数组 a，执行 n-1 趟扫描。第 i 趟（i=1..n-1）在 a[0]..a[n-i] 中通过相邻比较交换，将最大元素「冒泡」到 a[n-i] 位置。

逐轮演示（数组：2,0,3,6,8,4,9,5,1,7）

注意：第 7 趟已有序，但标准冒泡仍会执行第 8、9 趟（外层固定 n-1 次）。

标准实现

public void bubbleSort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {           // 外层 n-1 趟
        for (int j = 0; j < array.length - i - 1; j++) {   // 内层逐对比较
            if (array[j] > array[j + 1]) {
                int tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
            }
        }
    }
}

循环边界解析

• 外层：i = 0 .. n-2，共 n-1 趟，固定不变
• 内层：j = 0 .. n-i-2，比较 j 与 j+1，范围随 i 递减
• 比较总次数：(n-1)+(n-2)+...+1 = n(n-1)/2 = O(n²)

优化方向

1. 有序提前终止：引入 boolean swapped 标记，某趟无交换直接 break
2. 记录最后交换位置：下一趟只需扫描到最后交换位置，减少无效比较
3. 鸡尾酒排序：双向冒泡，解决「海龟」（小元素在右端）移动慢的问题

优化版代码

public void bubbleSortOptimized(int[] array) {
    int n = array.length;
    int lastSwap = n - 1;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        int currentLastSwap = 0;
        for (int j = 0; j < lastSwap; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
                swapped = true;
                currentLastSwap = j;
            }
        }
        if (!swapped) break;
        lastSwap = currentLastSwap;
    }
}

复杂度总结

面试加分点

• 能说出「稳定排序」定义：相等元素相对位置不变
• 能对比插入排序（适合近乎有序）、选择排序（交换次数少）
• 能手写优化版并解释 lastSwap 作用