算法与搜索排序

这一课你将能做到

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²)，工业实现用随机基准或三数取中规避。判题平台给用户代码做测试时，就可以故意构造这种极端输入检验其排序实现。