算法与搜索排序

这一课你将能做到

1. 说出冒泡、插入、选择、快排、归并排序的时间/空间复杂度与稳定性，并知道 Java 排序为什么是双实现
2. 手写二分查找及其变体，能判断一个问题是否具备二分前提
3. 用 BFS/DFS 遍历树与图，并识别双指针、滑动窗口两种高频解题模式

为什么要学

算法不是面试专用的智力体操，它是「给定输入，用有限步骤稳定拿到正确输出」的工程能力。判题平台本身就是算法产品：用户代码运行完，平台要把实际输出和标准答案逐字节比对（字符串匹配）；提交记录要按时间、分数排序展示；相似题推荐要在题目关系图上搜索；管理员要在百万提交记录里按 ID 快速定位——搜索和排序无处不在。

更重要的是，算法训练塑造一种思维：先问「数据有什么性质」（有序？有重复？范围多大？），再选步骤。本课覆盖复用率最高的一组基础算法，它们也是下一课复杂度分析的现成样本。

先建立图像

排序算法谱系
┌────────────┬────────────┬──────────────────────────┐
│ 冒泡/插入   │ 平均 O(n²) │ 直觉派：数据少或基本有序时快 │
│ /选择       │ 空间 O(1)  │ 插入排序是常数最小的 O(n²)  │
├────────────┼────────────┼──────────────────────────┤
│ 快速排序    │ 平均 O(nlogn)│ 分治：选基准，小左大右，递归│
│            │ 最坏 O(n²) │ 内存排序之王，原地、缓存友好 │
├────────────┼────────────┼──────────────────────────┤
│ 归并排序    │ 始终 O(nlogn)│ 分治：对半切，各自排，再合并│
│            │ 空间 O(n)  │ 稳定；外部排序/对象排序用它  │
└────────────┴────────────┴──────────────────────────┘

搜索
  顺序查找  O(n)    无前提
  二分查找  O(log n) 前提：有序 + 随机访问
  BFS      按层扩散，找「最短步数/最少跳数」，用队列
  DFS      一条路走到黑再回溯，用递归/栈，适合枚举全部可能

两个指针的艺术
  双指针：  11→        ←8        有序数组上对撞/同向推进
  滑动窗口：[▓▓▓▓]      窗口右扩左缩，解决连续子串/子数组问题

跟着做

步骤 1：写出快排并理解它为什么快

import java.util.Arrays;

public class QuickSort {

    public static void quickSort(int[] a, int left, int right) {
        if (left >= right) return;
        int p = partition(a, left, right);
        quickSort(a, left, p - 1);
        quickSort(a, p + 1, right);
    }

    private static int partition(int[] a, int left, int right) {
        int pivot = a[right];              // 选最右当基准
        int i = left;                      // i 指向「小区」的右边界之外
        for (int j = left; j < right; j++) {
            if (a[j] < pivot) {
                swap(a, i, j);
                i++;
            }
        }
        swap(a, i, right);                 // 基准归位
        return i;
    }

    private static void swap(int[] a, int x, int y) {
        int t = a[x];
        a[x] = a[y];
        a[y] = t;
    }

    public static void main(String[] args) {
        int[] scores = {88, 72, 95, 60, 72, 100};
        quickSort(scores, 0, scores.length - 1);
        System.out.println(Arrays.toString(scores));
    }
}

快排的思想是分治：partition 一趟下来，基准元素落定最终位置，左边都比它小、右边都比它大。平均每次对半切，切 log n 层、每层 O(n)，合计 O(n log n)。最坏情况（数组已有序且总取端点做基准）每次切出 0 和 n-1，退化 O(n²)，工业实现用随机基准或三数取中规避。判题平台给用户代码做测试时，就可以故意构造这种极端输入检验其排序实现。

步骤 2：看看 JDK 自己怎么排

import java.util.Arrays;

public class JdkSort {
    public static void main(String[] args) {
        int[] primitive = {5, 2, 9, 1, 5, 6};
        Arrays.sort(primitive);                 // 双轴快排（Dual-Pivot Quicksort）

        String[] objects = {"banana", "apple", "cherry"};
        Arrays.sort(objects);                   // TimSort：归并+插入，稳定排序
        System.out.println(Arrays.toString(primitive));
        System.out.println(Arrays.toString(objects));
    }
}

工程要点：基本类型排序不要求稳定，JDK 选缓存友好的快排变体；对象排序要求稳定性（相等元素保持业务原序，如先按时间排序的提交记录再按分数排，相同分数不应打乱时间顺序），所以用 TimSort。稳定性定义要记住：相等的元素排序后相对顺序不变。

步骤 3：二分查找——先排序，后折半

public class BinarySearch {

    // 标准二分：在有序数组中找 target，返回下标，找不到返回 -1
    public static int search(int[] a, int target) {
        int left = 0;
        int right = a.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;   // 防溢出，不要写 (left+right)/2
            if (a[mid] == target) {
                return mid;
            } else if (a[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] submissionIds = {1001, 1015, 1023, 1040, 2001};
        System.out.println(search(submissionIds, 1023));   // 2
        System.out.println(search(submissionIds, 9999));   // -1
    }
}

二分的本质不是「在数组上折半」，而是每问一个问题能排除一半可能性。所以链表上做二分没意义（拿到中间节点仍要 O(n)），而「猜数字」「在单调函数上找边界」「旋转数组找拐点」都能用。变体题（找第一个 ≥ target 的位置）只需把等号分支的处理和最终返回值改掉，循环条件的边界要靠不变量来保证。

步骤 4：BFS 找最短路径

设想题目之间有「前置题」关系，从入门题到目标题最少经过几道题：

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
import java.util.Map;

public class BfsDemo {
    public static void main(String[] args) {
        // 邻接表：题号 → 它推荐前往的下一题
        Map<String, List<String>> graph = Map.of(
            "入门", List.of("数组", "字符串"),
            "数组", List.of("链表", "栈"),
            "字符串", List.of("栈"),
            "链表", List.of("树"),
            "栈", List.of("树"),
            "树", List.of()
        );

        Deque<String> queue = new ArrayDeque<>();
        Deque<Integer> dist = new ArrayDeque<>();
        queue.offer("入门");
        dist.offer(0);

        while (!queue.isEmpty()) {
            String node = queue.poll();
            int d = dist.poll();
            System.out.println("到达 " + node + " 的最少题数: " + d);
            if (node.equals("树")) break;           // 首次到达即最短，可停
            for (String next : graph.get(node)) {
                queue.offer(next);
                dist.offer(d + 1);
            }
        }
    }
}

BFS 按层扩散，首次到达目标时路径一定最短（每条边代价相同的前提下）。生产代码通常用一个 Map<节点, 距离> 或节点带 level 字段，并配合 visited 防止重复入队。

步骤 5：滑动窗口——连续区间问题的通解

题目：找出提交记录连续通过（结果为 AC）的最长一段长度。

public class SlidingWindow {

    public static int longestAc(int[] results) {   // 1=AC，0=失败
        int left = 0;
        int longest = 0;
        for (int right = 0; right < results.length; right++) {
            while (results[right] == 0) {          // 右边界破坏条件时
                left = right + 1;                  // 左边界缩到合法位置
            }
            longest = Math.max(longest, right - left + 1);
        }
        return longest;
    }

    public static void main(String[] args) {
        System.out.println(longestAc(new int[]{1, 1, 0, 1, 1, 1}));  // 3
    }
}

模板套路：right 负责把元素纳入窗口，窗口不满足条件时移动 left 收缩，过程中更新答案。两个指针总共各走一遍，O(n)。双指针的另一形态「对撞指针」（有序两数之和：左小右大，和偏小就移左、偏大移右）是同一思想的变体。

讲清楚要点

1. 排序算法的三个评价维度：时间复杂度（最好/平均/最坏都要看）、空间复杂度（原地 O(1) 还是要辅助数组）、稳定性（相等元素保不保序）。
2. 快排赢在常数和缓存：平均 O(n log n) 且原地分区、访问连续；归并赢在稳定和最坏情况保证，以及天然适合外部排序（数据大到内存放不下，分段排序后多路归并）。
3. O(n²) 排序并非一无是处：插入排序在小数组（JDK 中阈值约 44/64）或近乎有序数据上极快，因为几乎只是比较不移动，所以 TimSort 把它当作小区间的收尾工具。
4. 二分的前提是「单调性 + 随机访问」，写对的关键是维护循环不变量（left/right 定义始终一致），left + (right-left)/2 防整数溢出是标准细节。
5. BFS 与 DFS 的选择：求最短/最少用 BFS（代价均等）；求任意可行解、枚举全部方案、检测环用 DFS；DFS 代码短但要注意递归深度，BFS 用队列可能占用大量内存（搜索树很宽时）。
6. 先想数据性质再选算法：数据有序 → 二分；范围有限且集中 → 计数排序 O(n+k)；只需要 Top K → 堆或快速选择，不必全排序。

你可能会懵的地方

• 稳定性到底有什么用？谁关心两个相等元素的先后？ 多关键字排序时关键。先按提交时间排，再按得分稳定排序，相同得分自然保持时间先后；数据库 ORDER BY a, b、报表分页都依赖这类语义。基本类型元素没有身份，所以快排即可。

• 快排平均 O(n log n) 凭什么，最坏情况真的会发生吗？ 平均指基准大致把数组对半分，递归树高 log n、每层总工作量 n。最坏在数组已有序且取端点为基准时必然发生；随机化基准后期望复杂度仍是 O(n log n)，所以工程上不用担心。

• DFS 用递归和用栈有什么区别？会栈溢出吗？ 逻辑等价。递归版本依赖 JVM 虚拟机栈（默认深度有限，常见几千到上万层），遍历十万节点的长链表会 StackOverflowError，改成显式 ArrayDeque 即可；BFS 不存在这个问题但队列可能很宽。

• 二分查找为什么总写错？ 根因是 left/right 的含义（闭区间还是半开区间）和更新方式不自洽。先在纸上写清「区间 [left, right] 始终包含候选答案」这条不变量，再严格按它写，就能一次写对。

• 算法题刷不动，是不是不够聪明？ 不是。算法是模式识别：排序分治、双指针、滑窗、BFS/DFS、回溯、动态规划，套路数量有限。初学者按专题各做 10 道并总结模板，比随机刷 200 道有效得多。

错法对照

错法	问题	正解
任意数组直接套二分	无序时结果不可信	先排序，或确认数据本身单调
mid = (left + right) / 2	大下标时整数溢出	left + (right - left) / 2
递归里忘记基准归位/递归边界	死递归或结果错误	left >= right 终止；partition 后跳过基准
BFS 不带 visited	环/共享邻居导致重复入队，指数膨胀	入队即标记或出队时判重
滑动窗口在 for 里每次重置 left	退化为 O(n²)	left 只前进不回退，保持窗口单调滑动

卡点急救

1. 提交列表排序后分页顺序错乱：检查排序是否稳定、第二排序字段是否唯一（补一个 id 作为最终 tiebreaker），数据库侧同样要加足 ORDER BY 字段。
2. 搜索类接口数据量一大就超时：先确认是不是在内存里全量遍历；有序数据用二分，动态数据用数据库索引/树结构，模糊搜索上倒排索引（ES）。
3. DFS/递归处理用户数据时栈溢出：对输入规模（如评论楼层深度、关系链长度）设上限，或改迭代写法；判题执行用户递归代码时容器内存和栈大小都要限制。

面试常问

• 常见排序算法的复杂度和稳定性？快排为什么快？ 冒泡/插入/选择平均 O(n²)、原地；快排平均 O(n log n)、最坏 O(n²)、原地不稳定；归并始终 O(n log n)、稳定、空间 O(n)。快排快在原地分区、访问连续、常数小，配合随机基准规避最坏情况。

• 二分查找的前提？手写并说明边界。 前提是数据有序且可随机访问。用闭区间 [left, right]，循环 left <= right，mid 防溢出，命中返回，否则 left=mid+1 或 right=mid-1；找不到时 left 即插入位置。

• BFS 和 DFS 的区别与应用？ BFS 队列实现、按层扩散，适合最短路径、层序处理；DFS 递归/栈实现、深入回溯，适合拓扑排序、环检测、全排列。判题平台的前置题最短链路用 BFS，导出全部题目树用 DFS。

自测三问

1. 不看表，默写出五种排序的最好/平均/最坏复杂度、空间与稳定性。
2. 给你一个百万级有序 ID 列表和每秒上千次查询，你会怎么实现查找？并发更新时又如何？
3. 哪些类型的问题让你立刻想到滑动窗口？说出它的循环骨架三要素。

小结一句话

搜索排序的智慧是「利用数据性质缩小搜索空间」：排序重排数据让二分成为可能，分治把大问题切成小问题，BFS/DFS 和窗口指针则用有限的遍历模式覆盖大量具体问题。

延伸

• 《算法导论》（CLRS）在线资源页——排序、搜索与分治分析的权威参考书
• Java 17 Arrays API 文档——sort 与 binarySearch 的官方契约
• VisuAlgo 排序与搜索动画
• 下一课：复杂度分析——你已经见过 O(n²)、O(n log n) 的反复出现，下一课系统学习 Big-O，把「快慢」变成可以计算和沟通的语言。