2026-05-31 排序算法三论：冒泡、选择与插入

一、为什么需要排序

借书系统的书架用 List<Item> 管理馆藏。数据有了，但顺序是乱的——想按逾期费从高到低排列、按书名字典序排列，书架做不到。排序是让数据”有序”的第一步。

二、冒泡排序（Bubble Sort）

直觉：相邻比较，大的往右换。像气泡一样，最大的数浮到最右端。

核心逻辑：

1. 从 index=0 开始，与相邻元素比较
2. 如果左边比右边大，交换
3. 一轮走完，最大数归位到最右端
4. 下一轮走到倒数第二（不需要再走到已归位的位置）

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

要点：内层 -i 是关键优化——已归位的元素不需要再比较。

三、选择排序（Selection Sort）

直觉：每轮挑最小的，放到对应位置。像挑豆子——坏的丢掉，好的装袋。

核心逻辑：

1. 设当前位置 i 为最小值位置（minIndex）
2. 从 i+1 往后扫，找到实际最小值
3. 与 i 位交换
4. 下一轮从 i+1 开始

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

四、复杂度对比

算法	比较次数	交换次数	特点
冒泡	O(n²)	O(n²)	相邻比就换，交换频繁
选择	O(n²)	O(n)	一轮只换一次，交换少

两者比较次数相同：n(n-1)/2。但选择的交换次数远少于冒泡——在交换代价高的场景下选择更优。

五、插入排序（Insertion Sort）

直觉：手里有一段排好的牌，每次抽一张新牌，插入到已排好段中的正确位置。

流程（已推完，代码待补）：

1. 从 index=1 开始抽牌（index=0 默认已排好）
2. 向左倒着比——遇到比自己大的就右移一格
3. 找到正确位置，插入

六、今日反思

今天下午递归+晚上排序，连续两节。冒泡和选择从直觉推到代码一气呵成——祥子说”算法思维的核心不是记代码，是能独立推导出过程”。三条推导路径全是自己走完的：冒泡从相邻比较到大数浮现，选择从挑最小到 minIndex 追踪，插入从手牌已排好到倒着比右移插入。

插入排序在最后一步掉链子了——流程全推完，代码写到一半大脑熄火。主动喊了停。以前不会喊停——会硬撑着敲，第二天看全是 bug。今晚的进步不是多学了一个算法，是知道什么时候该停下来。