背景

本文是Java修仙系列之数据结构与算法。若想详细学习修仙系列，请点击首篇博文，开始学习。

文章概览

  1. 数据结构
  2. 算法

一、数据结构

1. 数组

概念： 数组是固定长度、元素类型相同的线性序列。
特点：内存连续存储，支持索引随机访问（O(1)）。

核心特点：

  • 长度一旦创建不可改变
  • 内存连续分配
  • 通过下标（索引）快速访问元素
  • 所有元素类型必须一致

时间复杂度：

操作 时间复杂度 说明
访问 O(1) 通过索引直接定位，速度最快
搜索 O(n) 需要逐个遍历
插入 O(n) 可能需要移动后续元素
删除 O(n) 可能需要移动后续元素

示意图：

1
2
3
4

索引：   0   1   2   3   4
      ┌───┬───┬───┬───┬───┐
      │ 1 │ 2 │ 3 │ 4 │ 5 │
      └───┴───┴───┴───┴───┘

存储结构：

  • 线性结构
  • 顺序存储

优点：

  • 随机访问速度极快（O(1)）
  • 最简单、最基础的数据结构
  • 内存占用紧凑，无额外开销

缺点：

  • 长度固定，无法动态扩容
  • 插入、删除效率低（需要移动元素）

应用场景：

  • 需要快速查询、随机访问
  • 数据长度固定、不会频繁增删
  • 如：配置列表、查找表、排行榜、有序数列

Java 实现：

数组简易封装 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public class ArrayDemo {
    private int[] data;
    private int size;

    // 初始化数组，指定容量
    public ArrayDemo(int capacity) {
        this.data = new int[capacity];
        this.size = 0;
    }

    // 添加元素到末尾
    public void add(int value) {
        if (size == data.length) {
            throw new RuntimeException("数组已满，无法添加");
        }
        data[size++] = value;
    }

    // 根据索引获取元素
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界");
        }
        return data[index];
    }

    // 获取当前元素个数
    public int size() {
        return size;
    }

    public static void main(String[] args) {
        ArrayDemo arr = new ArrayDemo(5);
        arr.add(10);
        arr.add(20);
        arr.add(30);

        System.out.println("元素[1] = " + arr.get(1)); // 20
        System.out.println("当前元素个数 = " + arr.size()); // 3
    }
}

2. 链表

2.1 单向链表

概念：
由多个节点组成，每个节点只保存数据 + 后继指针 next，节点之间通过指针串联。
长度可动态变化，已知位置下插入/删除为 O(1)，不支持随机访问。

时间复杂度：

操作 时间复杂度
按索引访问 O(n)
查找元素 O(n)
头部插入 / 删除 O(1)
尾部插入 / 删除 O(n)
指定位置插入 / 删除 O(n)

示意图：

1

head → [1|●] → [2|●] → [3|●] → null

排队模型模拟链表反转

1

prev=null   cur=① → ② → ③ → ④ → null

第1轮

  1. next = ②（记住身后是②）
  2. ①.next = null（①向后转，没人可搭）
  3. prev = ①
  4. cur = ②

第1轮后：

1
2

null ← ①    ② → ③ → ④ → null
       prev  cur

第2轮

  1. next = ③
  2. ②.next = ①（②转过来搭①）
  3. prev = ②
  4. cur = ③

第2轮后：

1
2

null ← ① ← ②    ③ → ④ → null
            prev cur

循环结束！
最后 head = prev，也就是 head 指向 ④。

存储结构：线性结构、链式存储

优点：

  • 长度动态扩展，无需预设容量
  • 头部插入/删除极快 O(1)
  • 内存不要求连续，无空间浪费

缺点：

  • 不支持随机访问，查找必须从头遍历
  • 每个节点多存一个指针，略有额外开销

应用场景：

  • 频繁头尾增删、长度不确定
  • 实现栈、队列、邻接表、LRU 缓存

head是指针还是节点？

head 本身不是节点，head 是一个「引用/指针」，它指向 第一个节点。

场景：一排人排队

  • ①、②、③ 是真实的人（真实节点）
  • 有一个小牌子，上面写着 「队头」

这个牌子：

  • 不是人
  • 只是指向第一个人
1

队头牌子 → ① → ② → ③
  • 队头牌子 = head
  • ① = 第一个节点

回到 Java 代码

1

private Node<T> head;

这句话的真实意思是：

定义了一个 变量，名字叫 head， 它的类型是 Node， 它的作用是 保存第一个节点的地址

所以：

  • head 是引用变量
  • head 不是节点对象
  • head 指向的那个对象，才是真正的第一个节点

内存结构

1
2
3
4
5
6
7
8

【head 变量】      【节点① 对象】
   0x111     →     val=1, next=0x222

                  【节点② 对象】
                   val=2, next=0x333

                  【节点③ 对象】
                   val=3, next=null
  • head 只是一个存地址的盒子（0x111）
  • 盒子里装的是第一个节点的地址
  • 节点①才是真正的头节点

为什么只能从 head 入口？

  • 单链表只保存了 head 这一个引用
  • 中间节点、尾节点没有被全局记录
  • 如果你丢了 head，整个链表就“找不到了”，相当于数据丢失

一句话总结：
单链表只有一个入口：head 头节点。想要访问任何节点，都必须从 head 开始，一路顺着 next 找过去。

Java 实现：

单向链表 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165

// 导入Objects工具类，用于安全判断两个对象是否相等
import java.util.Objects;

/**
 * 通用单向链表实现（支持任意类型 T）
 * 只有 指针next，只能从头往后遍历
 */
public class SinglyLinkedList<T> {

    /**
     * 内部节点类：链表的最小单元
     * 每个节点存：数据 val + 下一个节点的引用 next
     */
    private static class Node<T> {
        T val;                // 节点存储的数据
        Node<T> next;         // 指向下一个节点的指针（引用）

        // 构造方法：创建节点时只需要传入数据
        Node(T val) {
            this.val = val;
        }
    }

    // 链表的头节点（第一个节点），只要知道head，就能找到整个链表
    private Node<T> head;

    /**
     * 头部添加元素（最快，O(1)）
     * 新节点变成新的头，指向原来的头
     */
    public void addFirst(T v) {
        Node<T> node = new Node<>(v);  // 1. 创建新节点
        node.next = head;             // 2. 新节点指向原来的头节点
        head = node;                  // 3. 更新头节点为新节点
    }

    /**
     * 尾部添加元素（O(n)）
     * 必须从头遍历到最后一个节点，再追加
     */
    public void addLast(T v) {
        Node<T> node = new Node<>(v);  // 1. 创建新节点

        // 如果链表为空，新节点直接当head
        if (head == null) {
            head = node;
        } else {
            Node<T> cur = head;        // 2. 从头开始遍历

            // 找到最后一个节点（next == null）
            while (cur.next != null) {
                cur = cur.next;
            }

            cur.next = node;          // 3. 最后一个节点指向新节点
        }
    }

    /**
     * 判断链表是否包含某个值（O(n)）
     */
    public boolean contains(T v) {
        Node<T> cur = head;           // 从头开始遍历

        while (cur != null) {
            // 安全比较两个对象是否相等
            if (Objects.equals(cur.val, v)) {
                return true;          // 找到就返回true
            }
            cur = cur.next;           // 继续下一个节点
        }
        return false;                 // 遍历完没找到
    }

    /**
     * 顺序打印链表所有元素
     */
    public void print() {
        // 从头遍历到尾
        for (Node<T> cur = head; cur != null; cur = cur.next) {
            System.out.print(cur.val + " ");
        }
        System.out.println();
    }

    /**
     * 迭代反转链表（最常用，面试高频）
     * 思路：把每个节点的next指针反过来指
     */
    public void reverse() {
        Node<T> prev = null;   // 前一个节点，初始null
        Node<T> cur = head;    // 当前节点，从头开始

        while (cur != null) {
            Node<T> next = cur.next;  // 1. 先保存下一个节点（防止断链）
            cur.next = prev;          // 2. 当前节点反过来指向前一个
            prev = cur;               // 3. prev 前进
            cur = next;               // 4. cur 前进
        }

        head = prev;  // 最后prev指向新头节点
    }

    /**
     * 递归反转链表（不改变外部head，仅返回新头）
     */
    public Node<T> reverseRecursive(Node<T> head) {
        // 递归终止条件：到最后一个节点
        if (head == null || head.next == null) {
            return head;
        }

        // 递归处理后面的链表
        Node<T> newHead = reverseRecursive(head.next);

        // 反转指针
        head.next.next = head;
        head.next = null;

        return newHead;  // 返回新的头节点
    }

    /**
     * 根据值删除节点（删除第一个匹配的值）
     */
    public void deleteByValue(T value) {
        // 空链表直接返回
        if (head == null) return;

        // 情况1：要删除的是头节点
        if (Objects.equals(head.val, value)) {
            head = head.next;  // 头节点后移一位即可删除
            return;
        }

        // 情况2：删除非头节点
        // 从头节点开始，找到【要删除节点的前一个节点】
        Node<T> cur = head;
        while (cur.next != null && !Objects.equals(cur.next.val, value)) {
            cur = cur.next;
        }

        // 如果找到了，让前一个节点跳过要删除的节点
        if (cur.next != null) {
            cur.next = cur.next.next;
        }
    }

    // 测试主方法
    public static void main(String[] args) {
        // 创建一个存储Integer类型的链表
        SinglyLinkedList<Integer> list = new SinglyLinkedList<>();

        list.addLast(5);      // 尾部添加 5
        list.addFirst(3);     // 头部添加 3
        list.addLast(7);      // 尾部添加 7
        list.print();         // 输出：3 5 7

        list.reverse();       // 反转链表
        list.print();         // 输出：7 5 3

        list.deleteByValue(5); // 删除值为5的节点
        list.print();          // 输出：7 3
    }
}

2.2 双向链表

概念：
每个节点包含数据 + 前驱指针 prev + 后继指针 next，支持双向遍历。
在已知节点的前提下，插入、删除、头尾操作均可达到 O(1)，是 Java LinkedList 的底层实现结构。

时间复杂度：

操作 时间复杂度
头部插入 / 删除 O(1)
尾部插入 / 删除 O(1)
指定节点删除 O(1)
按值查找 O(n)

示意图：

1
2

null ↔ [1] ↔ [2] ↔ [3] ↔ [4] ↔ null
       head              tail

优点：

  • 支持双向遍历，使用更灵活
  • 已知节点时，删除效率极高 O(1)
  • 头尾操作均为 O(1)，不用遍历

缺点：

  • 每个节点多一个前驱指针，内存开销略大于单链表
  • 查找仍需遍历，不支持随机访问

应用场景：

  • 浏览器前进、后退历史
  • 文本编辑器撤销/重做
  • Java 集合框架 LinkedList 底层实现

为什么双向链表只能从head和tail开始遍历？

  • 因为双向链表仅保存两个引用：head、tail
  • head 引用 → 指向第一个节点
  • tail 引用 → 指向最后一个节点
  • head、tail 都不是节点本身
  • 它们只是两个保存地址的变量

Java 实现：

双向链表 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

import java.util.Objects;

/**
 * 双向链表实现
 * 每个节点有：前驱 prev + 自身值 val + 后继 next
 * 可以从头走到尾，也可以从尾走到头
 */
public class DoublyLinkedList<T> {

    /**
     * 双向链表的节点类
     */
    private static class Node<T> {
        T val;                // 存的数据
        Node<T> prev;         // 指向前一个节点（前驱）
        Node<T> next;         // 指向后一个节点（后继）

        Node(T val) {
            this.val = val;
        }
    }

    // 双向链表维护两个指针：头 + 尾
    private Node<T> head;     // 头节点（最前面一个）
    private Node<T> tail;     // 尾节点（最后面一个）

    /**
     * 头部插入（加到最前面）
     */
    public void addFirst(T value) {
        Node<T> node = new Node<>(value);

        // 如果链表为空，头和尾都是这个新节点
        if (head == null) {
            head = tail = node;
        } else {
            // 新节点的后继指向原来的头
            node.next = head;
            // 原来的头的前驱指向新节点
            head.prev = node;
            // 更新头为新节点
            head = node;
        }
    }

    /**
     * 尾部插入（加到最后面）
     * 因为有 tail，所以不用遍历，直接插 O(1)
     */
    public void addLast(T value) {
        Node<T> node = new Node<>(value);

        // 链表为空，头尾都是它
        if (tail == null) {
            head = tail = node;
        } else {
            // 原来尾节点的后继指向新节点
            tail.next = node;
            // 新节点前驱指向原来的尾
            node.prev = tail;
            // 更新尾节点
            tail = node;
        }
    }

    /**
     * 判断是否包含某个值
     * 只能从头遍历，O(n)
     */
    public boolean contains(T value) {
        for (Node<T> cur = head; cur != null; cur = cur.next) {
            if (Objects.equals(cur.val, value)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 删除指定节点（直接传节点进来，O(1)）
     * 这是双向链表最大的优势
     */
    public void remove(Node<T> node) {
        // 情况1：只有这一个节点
        if (node == head && node == tail) {
            head = null;
            tail = null;
        }

        // 情况2：要删的是头节点
        else if (node == head) {
            // 头往后移
            head = head.next;
            // 新头的前驱置空
            head.prev = null;
        }

        // 情况3：要删的是尾节点
        else if (node == tail) {
            // 尾往前移
            tail = tail.prev;
            // 新尾的后继置空
            tail.next = null;
        }

        // 情况4：删除中间节点
        else {
            // 前一个节点的后继 跳过当前节点
            node.prev.next = node.next;
            // 后一个节点的前驱 跳过当前节点
            node.next.prev = node.prev;
        }
    }

    /**
     * 从头打印到尾
     */
    public void printForward() {
        for (Node<T> cur = head; cur != null; cur = cur.next) {
            System.out.print(cur.val + " ");
        }
        System.out.println();
    }

    /**
     * 从尾打印到头
     * 单链表做不到，双向链表可以
     */
    public void printBackward() {
        for (Node<T> cur = tail; cur != null; cur = cur.prev) {
            System.out.print(cur.val + " ");
        }
        System.out.println();
    }

    // 测试
    public static void main(String[] args) {
        DoublyLinkedList<Integer> list = new DoublyLinkedList<>();
        list.addLast(5);      // 尾部加5
        list.addFirst(3);     // 头部加3
        list.addLast(7);      // 尾部加7

        list.printForward();   // 3 5 7
        list.printBackward();  // 7 5 3
    }
}

3. 栈

概念：
栈是一种后进先出（LIFO = Last In First Out） 的线性数据结构。
就像叠盘子：最后放上去的，最先拿走。

核心特点：

  • 只能从 一头（栈顶） 添加、删除、查看
  • 另一头（栈底）不能操作
  • 所有操作都是 O(1) 极快

时间复杂度：

操作 时间复杂度 说明
push（入栈） O(1) 往栈顶放元素
pop（出栈） O(1) 从栈顶拿元素
peek（查看栈顶） O(1) 只看不删

示意图（叠盘子）：

1
2
3
4
5
6
7

push(1) → push(2) → push(3)

  [3]  ← 栈顶 top
  [2]
  [1]  ← 栈底 bottom

pop() → 拿走 3

应用场景：

  • 方法调用栈（Java 运行方法就是用栈）
  • 括号匹配问题 () [] {}
  • 浏览器后退、编辑器撤销
  • 表达式求值、计算器

Java 实现：

栈（数组实现 + 链表实现）
  1. 基于数组实现栈（固定容量）
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

// 基于数组实现的栈（容量固定）
public class ArrayStack<T> {
    private Object[] array;  // 存放数据的数组
    private int top;         // 栈顶指针：-1 = 空栈；0 = 第一个元素

    // 初始化栈，指定容量
    public ArrayStack(int capacity) {
        this.array = new Object[capacity];
        this.top = -1;       // 刚开始栈为空
    }

    // 入栈：往栈顶加元素
    public void push(T item) {
        if (isFull()) throw new IllegalStateException("栈满了");
        array[++top] = item; // top 先+1，再放元素
    }

    // 出栈：从栈顶取元素（删除并返回）
    public T pop() {
        if (isEmpty()) throw new IllegalStateException("栈空了");
        
        T item = (T) array[top];
        array[top--] = null; // 置空，避免内存泄漏，然后top-1
        return item;
    }

    // 查看栈顶元素（不删除）
    public T peek() {
        if (isEmpty()) throw new IllegalStateException("栈空了");
        return (T) array[top];
    }

    public boolean isEmpty() { return top == -1; }
    public boolean isFull()  { return top == array.length - 1; }

    public static void main(String[] args) {
        ArrayStack<Integer> stack = new ArrayStack<>(3);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        
        System.out.println(stack.pop());  // 3
        System.out.println(stack.peek()); // 2
    }
}
  1. 基于链表实现栈（无容量限制，更常用）
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

// 基于链表实现栈（自动扩容，无上限）
public class LinkedStack<T> {

    // 链表节点
    private static class Node<T> {
        T data;
        Node<T> next;
        Node(T data) { this.data = data; }
    }

    private Node<T> top; // 栈顶：永远指向链表头部

    // 入栈：往链表头部加（栈顶）
    public void push(T item) {
        Node<T> newNode = new Node<>(item);
        newNode.next = top;   // 新节点指向原来的栈顶
        top = newNode;        // 更新栈顶
    }

    // 出栈：删除链表头部
    public T pop() {
        if (isEmpty()) throw new IllegalStateException("栈空了");
        
        T data = top.data;   // 拿到栈顶数据
        top = top.next;      // 栈顶向下移动
        return data;
    }

    // 查看栈顶
    public T peek() {
        if (isEmpty()) throw new IllegalStateException("栈空了");
        return top.data;
    }

    public boolean isEmpty() { return top == null; }

    public static void main(String[] args) {
        LinkedStack<String> stack = new LinkedStack<>();
        stack.push("A");
        stack.push("B");
        stack.push("C");

        System.out.println(stack.pop());  // C
        System.out.println(stack.peek()); // B
    }
}

4. 队列

概念：
先进先出（FIFO = First In First Out）
像排队买票：先来的先走，后来的后走。

  • 队头（front）：出队
  • 队尾（rear）：入队

时间复杂度：

操作 Java 官方 队列时间复杂度 说明
enqueue（入队） offer O(1) 往队尾加
dequeue（出队） poll O(1) 从队头删

示意图：

1
2

dequeue ← [A]   [B]   [C] ← enqueue
         (队头)       (队尾)

应用场景：

  • 线程池任务排队
  • 消息队列
  • BFS 广度优先遍历
  • 排队系统

Java 实现：

队列实现（环形数组 + 链表）
  1. 环形数组实现（固定容量）
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

// 环形数组实现队列（固定容量）
public class CircularQueue<T> {
    private Object[] array;  // 存放数据
    private int front;      // 队头：要出队的位置
    private int rear;       // 队尾：要入队的位置
    private int size;       // 元素个数（简化判断）

    // 初始化队列
    public CircularQueue(int capacity) {
        array = new Object[capacity + 1]; // 多一个空位，区分空/满
        front = rear = size = 0;
    }

    // 入队：加到队尾
    public void enqueue(T item) {
        if (isFull()) throw new IllegalStateException("队列满了");
        
        array[rear] = item;          // 把数据放到队尾位置
        rear = (rear + 1) % array.length; // 队尾后移，环形循环
        size++;
    }

    // 出队：从队头拿走
    public T dequeue() {
        if (isEmpty()) throw new IllegalStateException("队列空了");

        T item = (T) array[front];    // 取出队头数据
        front = (front + 1) % array.length; // 队头后移
        size--;
        return item;
    }

    public boolean isEmpty() { return size == 0; }
    public boolean isFull()  { return size == array.length - 1; }

    public static void main(String[] args) {
        CircularQueue<String> q = new CircularQueue<>(5);
        q.enqueue("A");
        q.enqueue("B");
        q.enqueue("C");

        System.out.println(q.dequeue()); // A
        System.out.println(q.dequeue()); // B
    }
}

代码解释

什么是 环形数组？

你可以把数组想象成一个圈：

1
2
3

0 ← 5 ← 4
↓      ↑
1 → 2 → 3

走到最后一个位置后，自动回到开头，像时钟一样循环。

为什么要环形？ 因为普通数组出队后，前面的空间就浪费了， 环形数组可以重复利用空间。

为什么要写 capacity + 1？

一句话：为了区分 空队列 和 满队列

看这个你就秒懂

  • 队列空：front == rear
  • 队列满：如果不浪费一个位置，也会变成 front == rear

这样就分不清是空还是满了！

所以我们故意多开 1 个位置不用，用来区分：

1

array = new Object[capacity + 1];

你想要容量 5，我给你开 6 个位置，最后一个位置永远空着。

为什么满了是 size == array.length - 1

因为：

  • 数组总长度 = 你要的容量 + 1
  • 真正能存数据的位置 = 总长度 - 1

所以：

1
2
3

public boolean isFull() {
    return size == array.length - 1;
}

走一遍代码逻辑

假设你要容量 3 代码会创建数组长度 = 3+1=4

数组下标：0 1 2 3（3 号位置永远空着）

① 空队列

1
2
3

[ ] [ ] [ ] [ ]
 f
 r

front=0, rear=0

② 入队 A

1
2

[A] [ ] [ ] [ ]
 f   r

rear 往后走

③ 入队 B

1
2

[A][B] [ ] [ ]
 f      r

④ 入队 C → 队列满！

1
2

[A][B][C] [ ]
 f        r

size = 3
array.length - 1 = 4-1 = 3
所以 size == 3 → 满

rear = (rear + 1) % array.length; 到底啥意思？

先看普通情况（没走到头）
假设数组长度 = 4
rear 当前 = 1

1
2
3

rear = (1 + 1) % 4
     = 2 % 4
     = 2

正常往后走一步：1 → 2

走到头了！必须“环形”回到开头
rear 当前 = 3（最后一个位置）

1
2
3

rear = (3 + 1) % 4
     = 4 % 4
     = 0

从 3 → 直接回到 0
这就是环形循环！

  1. 链表实现队列（无容量限制，最常用）
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

// 链表实现队列（无容量限制）
public class LinkedQueue<T> {

    // 链表节点
    private static class Node<T> {
        T data;
        Node<T> next;
        Node(T data) { this.data = data; }
    }

    private Node<T> front;  // 队头：出队用
    private Node<T> rear;   // 队尾：入队用

    // 入队：加到链表尾部
    public void enqueue(T item) {
        Node<T> node = new Node<>(item);

        // 空队列 → 头和尾都指向新节点
        if (rear == null) {
            front = rear = node;
        } else {
            rear.next = node;  // 尾部指向新节点
            rear = node;       // 新节点变成新尾部
        }
    }

    // 出队：从链表头部拿走
    public T dequeue() {
        if (isEmpty()) throw new IllegalStateException("队列空了");

        T data = front.data;    // 取出队头数据
        front = front.next;     // 队头后移

        // 如果队列空了，rear 也置空
        if (front == null) {
            rear = null;
        }
        return data;
    }

    public boolean isEmpty() { return front == null; }

    public static void main(String[] args) {
        LinkedQueue<String> q = new LinkedQueue<>();
        q.enqueue("A");
        q.enqueue("B");

        System.out.println(q.dequeue()); // A
    }
}

代码解释

dequeue()方法中，为什么front = front.next对头后移就可以了，不需要A.next = null？

假设队列现在是：

1
2
3

front → A → B → C → null
         ↓
       原来的队头

执行这行代码：

1

front = front.next;

执行后变成：

1
2

         A → B → C → null
front → B

关键点来了

A 现在没有任何人引用它了！

  • 原来 front 指向 A
  • 现在 front 指向 B
  • A 变成了没人管的节点

那 A 的 next 还连着 B 重要吗？

不重要！完全不重要！

因为：

  • 我们再也不会访问 A 了
  • Java 发现没人用 A 了
  • 自动把 A 当成垃圾回收掉

你不需要写

1
2

// 根本不用写这个！
A.next = null;

只要做到

1

front = front.next;

就够了！

用生活例子你秒懂

你有一串钥匙：

1

钥匙串 → A钥匙 → B钥匙 → C钥匙

你把 A钥匙扔掉，只需要：

1

钥匙串 → B钥匙

A钥匙 自己就掉地上丢了
它连不连着 B 根本无所谓！

5. 哈希表

概念：
通过哈希函数把 key 转换成数组下标， 把键值对存到对应位置，实现近似 O(1) 快速查找、插入、删除。

核心思想：key → 哈希值 → 数组下标

时间复杂度：

操作 平均 最坏
插入 O(1) O(n)
查找 O(1) O(n)
删除 O(1) O(n)

哈希冲突：
两个不同 key 算出同一个下标 → 必须解决。

冲突解决方法：

  • 链地址法（最常用）：数组每个位置挂一个链表
  • 开放地址法：线性探测、二次探测

负载因子（重要）：
负载因子 = 元素个数 / 桶数组长度
默认 0.75
超过就自动扩容，保证查询效率。

示意图：

1
2
3
4
5

[桶数组]
[0] → null
[1] → (key1:val) → (key2:val)  → null （冲突链表）
[2] → (key3:val) → null
[3] → null

桶数组 = table 数组

代码里这句：

1

private Node<K, V>[] table;
  • table 就是桶数组
  • 桶数组 = 一个存节点引用的数组
  • 它的每一格，我们就叫一个桶（bucket）

桶数组里到底装不装东西？

装，但装的不是 KV，是“链表头”

结构是这样：

1
2
3
4
5
6
7

table（桶数组）
下标：
 0   →  null
 1   →  Node1 → Node2 → Node3 → null
 2   →  Node4 → null
 3   →  null
...
  • 桶数组[1] 里存的是：第一个节点的引用
  • Node1、Node2 内部才真正存 key 和 value

KV 到底存在哪？

存在 Node 里面！

1
2
3
4
5
6

private static class Node<K, V> {
    final K key;      // 真正的 key 存在这
    V value;          // 真正的 value 存在这
    Node<K, V> next;
    final int hash;
}

用生活类比

  • 桶数组 = 一排抽屉
  • 每个抽屉 = 一个桶
  • 抽屉里不放东西，只挂一根绳子
  • 绳子上串着很多小袋子
  • KV 存在小袋子里
1
2
3

抽屉0 → 没绳子
抽屉1 → 绳子 → 袋子(KV) → 袋子(KV)
抽屉2 → 绳子 → 袋子(KV)

应用场景：
键值对缓存、快速查找表、去重统计、Java HashMap、Redis 底层。

哈希表实现 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

import java.util.Objects;

public class HashMap<K, V> {

    // 默认桶数组大小（必须是2的幂）
    private static final int DEFAULT_CAPACITY = 16;

    // 负载因子
    private static final float LOAD_FACTOR = 0.75f;

    // 桶数组：每个位置是一个链表的头节点
    private Node<K, V>[] table;

    // 实际存储的键值对数量
    private int size;

    // 扩容阈值：size 超过这个值就扩容
    private int threshold;

    // 链表节点（存储 key、value、hash、下一个节点）
    private static class Node<K, V> {
        final K key;
        V value;
        Node<K, V> next;
        final int hash;

        Node(K key, V value, int hash, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    }

    // 构造方法：初始化桶数组
    @SuppressWarnings("unchecked")
    public HashMap() {
        table = (Node<K, V>[]) new Node[DEFAULT_CAPACITY];
        threshold = (int) (DEFAULT_CAPACITY * LOAD_FACTOR);
    }

    // 哈希函数：让哈希值更分散，减少冲突
    private int hash(K key) {
        if (key == null) return 0;
        int h = key.hashCode();
        return h ^ (h >>> 16);
    }

    // 计算数组下标：位运算代替取模，更快
    private int index(int hash) {
        return (table.length - 1) & hash;
    }

    // 添加/修改元素
    public void put(K key, V value) {
        int hash = hash(key);
        int index = index(hash);

        // 遍历链表，看 key 是否已经存在
        for (Node<K, V> node = table[index]; node != null; node = node.next) {
            if (node.hash == hash && Objects.equals(node.key, key)) {
                // 存在就覆盖 value
                node.value = value;
                return;
            }
        }

        // 不存在 → 头插法插入新节点
        table[index] = new Node<>(key, value, hash, table[index]);
        size++;

        // 超过阈值 → 扩容
        if (size > threshold) resize();
    }

    // 获取元素
    public V get(K key) {
        int hash = hash(key);
        int index = index(hash);

        // 遍历链表查找
        for (Node<K, V> node = table[index]; node != null; node = node.next) {
            if (node.hash == hash && Objects.equals(node.key, key)) {
                return node.value;
            }
        }
        return null; // 没找到
    }

    // 扩容：数组容量 ×2
    private void resize() {
        int newCapacity = table.length * 2;
        @SuppressWarnings("unchecked")
        Node<K, V>[] newTable = (Node<K, V>[]) new Node[newCapacity];
        threshold = (int) (newCapacity * LOAD_FACTOR);

        // 把旧数组的所有节点重新计算下标，放到新数组
        for (Node<K, V> node : table) {
            while (node != null) {
                Node<K, V> next = node.next;
                int newIndex = (newCapacity - 1) & node.hash;

                // 头插法插入新数组
                node.next = newTable[newIndex];
                newTable[newIndex] = node;

                node = next;
            }
        }
        table = newTable;
    }

    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("apple", 10);
        map.put("banana", 20);
        System.out.println(map.get("apple"));  // 10
        System.out.println(map.get("grape"));  // null
    }
}

代码解释

这个类 HashMap，是不是就是哈希表？

是的！完全是！

  • 哈希表（Hash Table）是数据结构名字
  • HashMap 是哈希表在 Java 里的具体实现类名

可以理解成：

  • 哈希表 = 概念
  • HashMap = 代码实现

就像：

  • 栈 = 概念
  • ArrayStack = 写的实现

所以： 写的这个 HashMap，就是一个标准的哈希表。

6. 树

6.1 二叉树

概念：
每个节点最多两个子节点，分为左孩子、右孩子。
是所有树形结构的基础。

基本概念：

  • 根节点（root）：最顶层节点
  • 叶子节点：没有孩子的节点
  • 深度：从根到当前节点的层数
  • 高度：从当前节点到最深叶子的层数

遍历方式（必考）：

  • 前序：根 → 左 → 右
  • 中序：左 → 根 → 右
  • 后序：左 → 右 → 根
  • 层序：按从上到下、从左到右遍历（队列实现）

节点内存结构：

  • val
  • left 指针
  • right 指针

整棵树的结构逻辑是

  • 我自己这个节点 = 根
  • 我的左边挂着一棵更小的树 = 左子树
  • 我的右边挂着一棵更小的树 = 右子树

它是从结构视角说的， 不是从节点内存结构说的。

高度（Height） vs 深度（Depth）

高度 = 从自己往下看
深度 = 从根往下看

1
2
3
4
5

        x   ← 根
         \
          z
           \
            y  ← 叶子

算 高度

从【当前节点】往下数 → 到叶子节点的最长层数

  • y：下面没节点 → 高度 = 1
  • z：下面有1层 → 高度 = 2
  • x：下面有2层 → 高度 = 3

从【根节点】往下数 → 到当前节点的层数

算 深度

  • x：深度 1
  • z：深度 2
  • y：深度 3

应用：
表达式树、二叉搜索树、堆、AVL、红黑树的基础结构。

Java 实现：

二叉树 & 四种遍历 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

import java.util.*;
public class BinaryTree {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    // 前序：根 → 左 → 右
    public void preOrder(TreeNode root) {
        if (root == null) return;
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序：左 → 根 → 右
    public void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    // 后序：左 → 右 → 根
    public void postOrder(TreeNode root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    // 层序：按层遍历（队列）
    public void levelOrder(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            System.out.print(node.val + " ");
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        BinaryTree tree = new BinaryTree();
        tree.preOrder(root);    // 1 2 3
    }
}

解释层序遍历

先把 root 放进去 再把 root 拿出来打印 同时把 root 的左右子树放进队列 再循环拿出下一个节点打印

假设有这棵树：

1
2
3
4
5

        1
       / \
      2   3
     / \
    4  5

第一步：先把根节点 1 入队

1

队列：[ 1 ]

第二步：进入循环

① 出队 1 → 打印

1

打印：1

把 1 的左、右孩子 2、3 入队

1

队列：[ 2, 3 ]

② 出队 2 → 打印

1

打印：1 2

把 2 的左、右孩子 4、5 入队

1

队列：[ 3, 4, 5 ]

③ 出队 3 → 打印

1

打印：1 2 3

3 没有孩子 → 不入队

1

队列：[ 4, 5 ]

④ 出队 4 → 打印

1

打印：1 2 3 4

无孩子

1

队列：[5]

⑤ 出队 5 → 打印

1

打印：1 2 3 4 5

最终结果

1 2 3 4 5 从上到下、从左到右，一层一层遍历！

6.1 二叉搜索树（BST）

概念：
一棵二叉树，满足：

  • 左子树所有节点值 < 根节点
  • 右子树所有节点值 > 根节点
  • 中序遍历结果一定是升序序列

时间复杂度：

操作 平均（平衡） 最坏（链化）
查找 O(log n) O(n)
插入 O(log n) O(n)
删除 O(log n) O(n)

特点：
实现简单，但有序插入会退化成链表，效率暴跌。
解决办法：使用自平衡二叉搜索树（AVL / 红黑树）。

示意图：

1
2
3
4
5

        5
       / \
      3   8
     / \   \
    2   4   9

应用场景：有序数据存储、查找、数据库索引（B+树）。

Java 实现：

二叉搜索树 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

public class BinarySearchTree {

    // 二叉树节点：每个节点存 值 + 左孩子 + 右孩子
    private static class TreeNode {
        int val;                // 节点存的数字
        TreeNode left, right;   // 左、右孩子指针（引用）
        TreeNode(int val) { this.val = val; }
    }

    private TreeNode root;  // 整棵树的根节点（入口）

    // ====================== 插入 ======================
    // 对外提供的插入方法
    public void insert(int val) {
        // 调用递归插入，把新树赋值给 root
        root = insertRecursive(root, val);
    }

    // 递归插入：把值插入到正确位置
    private TreeNode insertRecursive(TreeNode node, int val) {
        // 递归终止条件：走到空位置，直接新建节点放这里
        if (node == null) return new TreeNode(val);

        // 要插入的值 < 当前节点 → 往左子树插
        if (val < node.val) {
            node.left = insertRecursive(node.left, val);
        }
        // 要插入的值 > 当前节点 → 往右子树插
        else if (val > node.val) {
            node.right = insertRecursive(node.right, val);
        }

        // 相等不处理（不允许重复值）
        // 返回当前节点，维持树结构
        return node;
    }

    // ====================== 查找 ======================
    // 对外提供的查找方法
    public boolean search(int val) {
        return searchRecursive(root, val);
    }

    // 递归查找
    private boolean searchRecursive(TreeNode node, int val) {
        // 走到空都没找到 → 返回 false
        if (node == null) return false;

        // 找到了 → 返回 true
        if (val == node.val) return true;

        // 比当前小 → 去左边找
        // 比当前大 → 去右边找
        return val < node.val
            ? searchRecursive(node.left, val)
            : searchRecursive(node.right, val);
    }

    // ====================== 删除（最难） ======================
    // 对外提供的删除方法
    public void delete(int val) {
        root = deleteRecursive(root, val);
    }

    // 递归删除
    private TreeNode deleteRecursive(TreeNode node, int val) {
        // 空节点 → 不用删
        if (node == null) return null;

        // 要删的值 < 当前节点 → 去左边删
        if (val < node.val) {
            node.left = deleteRecursive(node.left, val);
        }
        // 要删的值 > 当前节点 → 去右边删
        else if (val > node.val) {
            node.right = deleteRecursive(node.right, val);
        }
        // 找到了要删除的节点！
        else {
            // 情况1：没有左孩子 → 直接用右孩子顶替自己
            if (node.left == null) return node.right;
            // 情况2：没有右孩子 → 直接用左孩子顶替自己
            if (node.right == null) return node.left;

            // 情况3：左右孩子都有（最难）
            // 找 右子树中最小的节点（后继节点）来顶替自己
            TreeNode successor = findMin(node.right);
            node.val = successor.val;  // 把值替换过来

            // 删掉那个顶替我的后继节点
            node.right = deleteRecursive(node.right, successor.val);
        }

        return node;
    }

    // 找到一棵树里最小的节点（一直往左走到底）
    private TreeNode findMin(TreeNode node) {
        while (node.left != null) node = node.left;
        return node;
    }

    // ====================== 中序遍历（输出升序） ======================
    public void inorder() {
        inorderRecursive(root);
        System.out.println();
    }

    // 中序：左 → 根 → 右
    private void inorderRecursive(TreeNode node) {
        if (node != null) {
            inorderRecursive(node.left);   // 先遍历左边
            System.out.print(node.val + " "); // 打印自己
            inorderRecursive(node.right);  // 再遍历右边
        }
    }

    // ====================== 测试 ======================
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        // 插入一组数字
        int[] vals = {5, 3, 7, 2, 4, 6, 8};
        for (int v : vals) bst.insert(v);

        // 中序遍历一定是升序
        bst.inorder(); // 2 3 4 5 6 7 8

        // 查找 4
        System.out.println("查找4: " + bst.search(4)); // true

        // 删除 3
        bst.delete(3);
        bst.inorder(); // 2 4 5 6 7 8
    }
}

代码解释

先给出一棵固定的树

1
2
3
4
5

        5
      /   \
     3     7
    / \   / \
   2   4 6   8

按照 5 → 3 → 7 → 2 → 4 → 6 → 8 的顺序，一个个放进树里

整段代码总解释

1

public class BinarySearchTree {}

这就是一个二叉搜索树，规则：
小的放左边，大的放右边。

节点是什么？

1
2
3
4
5

private static class TreeNode {
    int val;         // 存的数字
    TreeNode left;   // 左孩子（更小）
    TreeNode right;  // 右孩子（更大）
}

一个节点 = 一个值 + 两个指针（左、右）

插入 insert

1
2
3

public void insert(int val) {
    root = insertRecursive(root, val);
}

规则：

  • 比我小 → 往左走
  • 比我大 → 往右走
  • 走到空 → 新建节点

查找 search

1

public boolean search(int val)
  • 小 → 左
  • 大 → 右
  • 找到 → true
  • 空 → false

删除 delete

我们要删除的节点：3

1
2
3
4
5

        5
      /   \
    [3]    7
    / \   / \
   2   4 6   8

删除 3 会遇到什么情况？

3 有两个孩子：左 2，右 4
这是最难的第三种情况！

我开始一步一步执行 delete(3)

第一轮：从根节点 5 开始
因为：我们手里只握着根节点 5，别的节点都找不到！

1

deleteRecursive(5, 3)

要删的是 3
3 < 5 → 去左边找

1

node.left = deleteRecursive(3, 3)

第二轮：来到节点 3

1

deleteRecursive(3, 3)

终于找到要删的节点 3 了！

现在判断：

  • 3 有左孩子 2
  • 3 有右孩子 4

→ 两个孩子都存在！进入情况 3

最关键步骤来了

步骤 1：找后继节点（右子树最小的）

要删 3，它的右子树是 4

1

findMin(4) → 一直往左走 → 就是 4

后继节点 = 4

步骤 2：把后继节点的值 覆盖 到 3 上

1

node.val = successor.val;

原来的 3 → 变成 4

树现在变成：

1
2
3
4
5

        5
      /   \
     4     7
    / \   / \
   2   4 6   8

注意：右边那个 4 还在！

步骤 3：删除原来的那个后继节点 4

1

node.right = deleteRecursive(4, 4) // 第一个参数是右下角的 4

现在去删 右子树中的 4

第三轮：删除 4

1

deleteRecursive(4, 4)

4 没有左孩子 所以直接返回它的右孩子（null）

1

return null;

于是：

1

4 的位置变成 null

最终树变成了

1
2
3
4
5

        5
      /   \
     4     7
    /     / \
   2     6   8

中序遍历： 2 4 5 6 7 8

陷阱：
如果你按 1、2、3、4、5 这种有序顺序插入 BST，
树不会分叉，会直接变成一条“斜链子”，
查找就跟遍历链表一样慢，从 O(log n) 退化成 O(n)。
解决方案：使用自平衡树（AVL、红黑树）。

1
2
3
4
5
6
7
8
9

1
 \
  2
   \
    3
     \
      4
       \
        5

6.2 AVL 树（自平衡二叉搜索树）

一、概念

带有平衡因子的二叉搜索树。

  • 平衡因子 = 当前节点的左子树高度 − 当前节点的右子树高度
  • 任何节点的平衡因子只能是：−1、0、1
  • 超出范围就通过旋转自动平衡

二、平衡方式

  1. 右旋（右单旋）→ 解决 LL 左左倾斜

现象
左边太高，整条链都往左左偏

1
2
3
4
5

      y
     /
    x
   /
  z

旋转对象
对 y 节点右旋，旋转中心是：y

旋转后

1
2
3

    x
   / \
  z   y

右旋规则

  • 把 x 提上来当新父
  • y 变成 x 的右孩子
  • x 原来的右孩子挂到 y 的左边
  • x 的左孩子全程不动
  1. 左旋（左单旋）→ 解决 RR 右右倾斜

现象
右边太高，整条链都往右右偏

1
2
3
4
5

  x
   \
    y
     \
      z

旋转对象
对 x 节点左旋，旋转中心是：x

旋转后

1
2
3

    y
   / \
  x   z

左旋规则

  • 把 y 提上来当新父
  • x 变成 y 的左孩子
  • y 原来的左孩子挂到 x 的右边
  • y 的右孩子全程不动
  1. 左右旋（LR）→ 先左旋，再右旋

现象
左子树高，但新节点 z 插在左孩子的右边

1
2
3
4
5

      y
     /
    x
     \
      z

（1）类型判断

  1. 先看失衡节点 y
  2. 看新节点 z 走的路径
    • 从 y 出发 → 先 左 → 再 右
    • → 左 → 右 → 缩写 LR
  3. 结构 = LR 型

（2）旋转步骤

规则
LR = 先对 x 左旋 → 再对 y 右旋

原始树

1
2
3
4
5

        y
       /
      x
       \
        z

① 对 x 左旋
这里的关系是：y.left = x
执行：

1

node.left = leftRotate(x);

等价于：

1

y.left = leftRotate(x);

leftRotate(x) 返回节点 z，即：

1

y.left = z;

结构变为：

1
2
3
4
5

        y
       /
      z   ← 因为 y.left 被赋值成 z 了
     /
    x

此时变为 LL 型。

② 对 y 右旋 旋转后平衡：

1
2
3

      z
     / \
    x   y
  1. 右左旋（RL）→ 先右旋，再左旋

现象
右子树高，但新节点 z 插在右孩子的左边

1
2
3
4
5

      x
       \
        y
       /
      z

（1）类型判断

  1. 先看失衡节点 x
  2. 看新节点 z 走的路径
    • 从 x 出发 → 先 右 → 再 左
    • → 右 → 左 → 缩写 RL
  3. 结构 = RL 型

（2）旋转步骤

规则
RL = 先对 y 右旋 → 再对 x 左旋

原始树

1
2
3
4
5

        x
         \
          y
         /
        z

① 对 y 右旋
这里的关系是：x.right = y
执行：

1

node.right = rightRotate(y);

等价于：

1

x.right = rightRotate(y);

rightRotate(y) 返回节点 z，即：

1

x.right = z;

结构变为：

1
2
3
4
5

        x
         \
          z
           \
            y

此时变为 RR 型。

② 对 x 左旋 旋转后平衡：

1
2
3

      z
     / \
    x   y

三、复杂度

查找 / 插入 / 删除 稳定 O(log n)，不会退化成链表。

四、优点

  • 严格平衡
  • 查找速度极快，比红黑树略快

五、缺点

  • 插入删除旋转频繁，维护成本高
  • 不适合频繁修改的场景

六、应用场景

查找密集型、插入删除较少的场景。

Java 实现：

AVL 树完整代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112

public class AVLTree {

    // AVL 树节点：比普通 BST 多了一个 height 高度字段
    static class Node {
        int val;      // 节点值
        int height;   // 高度：用于计算平衡因子
        Node left;    // 左孩子
        Node right;   // 右孩子

        Node(int val) {
            this.val = val;
            this.height = 1; // 新建节点高度默认为 1
        }
    }

    private Node root; // 整棵树的根节点

    // ====================== 工具方法 ======================

    // 获取节点高度，空节点高度为 0
    private int height(Node n) {
        return n == null ? 0 : n.height;
    }

    // 计算平衡因子 = 左子树高度 - 右子树高度
    // 必须在 -1、0、1 之间，否则失衡
    private int balance(Node n) {
        return n == null ? 0 : height(n.left) - height(n.right);
    }

    // ====================== 右旋（解决 LL 失衡） ======================
    private Node rightRotate(Node y) {
        Node x = y.left;       // x 是 y 的左孩子
        Node t2 = x.right;     // t2 是 x 的右子树

        // 右旋操作
        x.right = y;           // y 变成 x 的右孩子
        y.left = t2;           // t2 变成 y 的左孩子

        // 更新高度
        y.height = Math.max(height(y.left), height(y.right)) + 1;
        x.height = Math.max(height(x.left), height(x.right)) + 1;

        return x; // x 成为新的根
    }

    // ====================== 左旋（解决 RR 失衡） ======================
    private Node leftRotate(Node x) {
        Node y = x.right;       // y 是 x 的右孩子
        Node t2 = y.left;       // t2 是 y 的左子树

        // 左旋操作
        y.left = x;            // x 变成 y 的左孩子
        x.right = t2;          // t2 变成 x 的右孩子

        // 更新高度
        x.height = Math.max(height(x.left), height(x.right)) + 1;
        y.height = Math.max(height(y.left), height(y.right)) + 1;

        return y; // y 成为新的根
    }

    // ====================== 插入节点（带自动平衡） ======================
    public Node insert(Node node, int val) {
        // 1. 标准 BST 插入
        if (node == null)
            return new Node(val);

        if (val < node.val)
            node.left = insert(node.left, val);      // 小 → 左
        else if (val > node.val)
            node.right = insert(node.right, val);    // 大 → 右
        else
            return node; // 重复值不处理

        // 2. 更新当前节点高度
        node.height = 1 + Math.max(height(node.left), height(node.right));

        // 3. 计算平衡因子，判断是否失衡
        int bal = balance(node);

        // 4. 处理 4 种失衡情况

        // LL 型：左左 → 右旋修复
        if (bal > 1 && val < node.left.val)
            return rightRotate(node);

        // RR 型：右右 → 左旋修复
        if (bal < -1 && val > node.right.val)
            return leftRotate(node);

        // LR 型：左右 → 先左旋左子树，再右旋
        if (bal > 1 && val > node.left.val) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // RL 型：右左 → 先右旋右子树，再左旋
        if (bal < -1 && val < node.right.val) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        // 没有失衡，直接返回节点
        return node;
    }

    // 对外提供的添加方法
    public void add(int val) {
        root = insert(root, val);
    }
}

6.3 红黑树（弱平衡二叉搜索树）

一、概念

一种自平衡二叉搜索树，通过颜色规则 + 旋转保持大致平衡。
不追求绝对平衡，只保证黑色节点完美平衡。

二、节点颜色规则

  1. 每个节点只能是 红 / 黑
  2. 根节点永远黑色
  3. 所有空节点（null）= 黑色
  4. 红色节点它的孩子必须都是黑色 → 不能出现连续两个红
1
2
3
4
5

    黑
    \
        红   ← 父
        \
        红  ← 子 → 连续红！违规！
  1. 任何路径的黑色节点数量完全相同
1
2
3
4
5

         黑
       /    \
      红      黑
     /  \    /
    黑   黑 红
  1. 根 → 红左 → 黑 黑色：根 + 最左黑 = 2 个
  2. 根 → 红右 → 黑 黑色：根 + 最右黑 = 2 个
  3. 根 → 黑 → 红 黑色：根 + 右边黑 = 2 个

全部都是 2 个黑 → 合法！

三、核心特点

  • 比 AVL 更宽松：不绝对平衡
  • 旋转更少，插入/删除更快
  • 综合性能最强
  • 工业界实际使用最多

四、复杂度

所有操作稳定 O(log n)

五、应用场景（超级重要）

  • Java TreeMap / TreeSet 底层
  • C++ std::map / std::set
  • Linux 进程调度、内存管理
  • 数据库索引（常用）

六、节点插入规则

  1. 新节点默认红色
  2. 只有 父节点是红色 才需要修复
  3. 修复方式：变色 + 旋转

七、节点修复规则

修复时的角色定位

  • z：自己（新节点）
  • 父：z.parent
  • 祖父：父.parent
  • 叔叔：祖父的另一个孩子（不是父的那个）

情况1：叔叔是红色 → 只变色，不旋转

  • 父变黑
  • 叔叔变黑
  • 祖父变红
  • z 往上跳到祖父，继续检查

情况2：叔叔是黑色 + LL / RR → 单旋

  • 父变黑
  • 祖父变红
  • 对祖父旋转

情况3：叔叔是黑色 + LR / RL → 双旋

  • 先对父旋转
  • 再对祖父旋转
  • 变色：父变黑，祖父变红

八、红黑树 4 种调整情况

1
2
3
4
5

        黑(B)        ← 祖父 (Grandpa)
       /    \
      红(R)  红(R)   ← 父(左)   叔叔(右)
     /
    红(R)            ← 自己 (新节点)

一眼对应

  • 最上面那个黑 B = 祖父
  • 祖父的左孩子 R = 爸爸（父节点）
  • 祖父的右孩子 R = 叔叔
  • 爸爸下面的 R = 自己（新节点 z）

超级固定规则，红黑树调整时

  1. 自己在最下面
  2. 爸爸在自己上面
  3. 祖父在爸爸上面
  4. 叔叔 = 祖父的另一个孩子
    • 爸爸在左 → 叔叔在右
    • 爸爸在右 → 叔叔在左

红黑树 4 种调整情况

  1. 叔叔是红色 → 只变色，不旋转
1
2
3
4
5

        黑(B)
       /    \
      红(R)  红(R)  ← 叔叔是红
     /
    红(R)       ← 新节点

做法：

  • 父、叔变黑
  • 祖父变红
  • 继续向上检查
  1. 叔叔是黑色 + 左左（LL）→ 右旋

这里叔叔根本不是正常节点，它是一个虚拟的黑色空节点 NIL。图里根本没画叔叔，但他是存在的！
更不是叶子节点，只是红黑树规定：所有空位置都视为黑色叶子。

1
2
3
4
5

        黑(B)
       /
      红(R)
     /
    红(R)

做法：

  • 对 祖父右旋
  • 父变黑，祖父变红
  1. 叔叔是黑色 + 右右（RR）→ 左旋
1
2
3
4
5

    黑(B)
     \
      红(R)
       \
        红(R)

做法：

  • 对 祖父左旋
  • 父变黑，祖父变红
  1. 叔叔是黑色 + 左右（LR）→ 左旋 + 右旋
1
2
3
4
5

        黑(B)
       /
      红(R)
       \
        红(R)

做法：

  • 对 父左旋
  • 对 祖父右旋
  1. 叔叔是黑色 + 右左（RL）→ 右旋 + 左旋
1
2
3
4
5

    黑(B)
     \
      红(R)
     /
    红(R)

做法：

  • 对 父右旋
  • 对 祖父左旋

Java 实现：

红黑树完整代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

public class RedBlackTree {
    // 定义颜色
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    // 红黑树节点结构
    static class Node {
        int val;
        Node left, right, parent; // 比AVL多了parent父节点
        boolean color;

        Node(int val) {
            this.val = val;
            this.color = RED; // 新节点一定是红色
        }
    }

    private Node root;

    // ======================== 左旋（和AVL一样！） ========================
    private void leftRotate(Node x) {
        Node y = x.right;  // y是x的右孩子
        x.right = y.left;  // y的左孩子挂到x右边

        if (y.left != null)
            y.left.parent = x;

        y.parent = x.parent; // y继承x的父亲

        if (x.parent == null)
            root = y;        // x是根，y变成新根
        else if (x == x.parent.left)
            x.parent.left = y;
        else
            x.parent.right = y;

        y.left = x;
        x.parent = y;
    }

    // ======================== 右旋（和AVL一样！） ========================
    private void rightRotate(Node y) {
        Node x = y.left;   // x是y的左孩子
        y.left = x.right;  // x的右孩子挂到y左边

        if (x.right != null)
            x.right.parent = y;

        x.parent = y.parent; // x继承y的父亲

        if (y.parent == null)
            root = x;         // y是根，x变成新根
        else if (y == y.parent.right)
            y.parent.right = x;
        else
            y.parent.left = x;

        x.right = y;
        y.parent = x;
    }

    // ======================== 插入后修复（红黑树核心） ========================
    private void fixInsert(Node z) {
        while (z.parent != null && z.parent.color == RED) { // 父是红才调整
            if (z.parent == z.parent.parent.left) {
                Node uncle = z.parent.parent.right; // 叔叔节点

                // 情况1：叔叔是红色 → 变色
                if (uncle != null && uncle.color == RED) {
                    z.parent.color = BLACK;
                    uncle.color = BLACK;
                    z.parent.parent.color = RED;
                    z = z.parent.parent;
                } else {
                    // 情况2：叔叔黑色 + LR
                    if (z == z.parent.right) {
                        z = z.parent;
                        leftRotate(z);
                    }
                    // 情况3：叔叔黑色 + LL
                    z.parent.color = BLACK;
                    z.parent.parent.color = RED;
                    rightRotate(z.parent.parent);
                }
            } else {
                // 镜像逻辑：右边
                Node uncle = z.parent.parent.left;

                // 情况1
                if (uncle != null && uncle.color == RED) {
                    z.parent.color = BLACK;
                    uncle.color = BLACK;
                    z.parent.parent.color = RED;
                    z = z.parent.parent;
                } else {
                    // 情况2：RL
                    if (z == z.parent.left) {
                        z = z.parent;
                        rightRotate(z);
                    }
                    // 情况3：RR
                    z.parent.color = BLACK;
                    z.parent.parent.color = RED;
                    leftRotate(z.parent.parent);
                }
            }
        }
        root.color = BLACK; // 根永远黑色
    }

    // ======================== BST 插入 + 红黑调整 ========================
    public void insert(int val) {
        Node newNode = new Node(val);
        Node parent = null;
        Node current = root;

        while (current != null) {
            parent = current;
            if (val < current.val) current = current.left;
            else current = current.right;
        }

        newNode.parent = parent;

        if (parent == null) root = newNode;
        else if (val < parent.val) parent.left = newNode;
        else parent.right = newNode;

        fixInsert(newNode); // 插入后修复
    }
}

代码解释

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

private void leftRotate(Node x) {
    Node y = x.right;              // 1. 记录y
    x.right = y.left;              // 2. y的左孩子给x.right

    if (y.left != null)
        y.left.parent = x;         // 3. y左孩子认x当父

    y.parent = x.parent;           // 4. y继承x的父亲（爷爷）

    if (x.parent == null)
        root = y;                  // 5. x是根 → y变根
    else if (x == x.parent.left)
        x.parent.left = y;         // 6. x是爷爷左孩子 → y代替x
    else
        x.parent.right = y;        // 7. x是爷爷右孩子 → y代替x

    y.left = x;                   // 8. x变成y的左孩子
    x.parent = y;                 // 9. x认y当父
}

左旋（x 是要旋转的节点）

  1. 先记录 y，y 是 x 的右孩子
  2. 把 y 的左孩子 拿下来，挂给 x 的右孩子
  3. 让 y 的左孩子 认 x 当爸爸
  4. 让 x 原来的爸爸（爷爷） 变成 y 的爸爸
  5. 如果 x 本来没有爸爸（x 是根），那 y 变成新根
  6. 如果 x 是爷爷的左孩子 → 让爷爷的左孩子 = y
  7. 如果 x 是爷爷的右孩子 → 让爷爷的右孩子 = y
  8. 让 x 变成 y 的左孩子
  9. 让 y 变成 x 的爸爸

最终最精简 4 步

  1. y 的左孩子过继给 x
  2. y 认爷爷当爸爸
  3. 爷爷把原来挂 x 的位置，换成挂 y
  4. x 认 y 当新爸爸

6.4 堆（完全二叉树）

一、概念

  • 堆是一棵完全二叉树，就是绝对不能出现 “左边空、右边有”的情况！必须都填满。
  • 采用数组存储（最核心特点）
  • 分为两种：
    1. 最大堆：父节点 ≥ 子节点，堆顶最大
    2. 最小堆：父节点 ≤ 子节点，堆顶最小

二、数组下标关系（索引从 0 开始）

1
2
3

父节点索引：(i - 1) / 2
左孩子索引：2 * i + 1
右孩子索引：2 * i + 2

i 就是「当前这个节点」在数组里的下标（位置编号）

数组：[1, 3, 2, 7, 9, 8, 4]
下标：0 1 2 3 4 5 6

对应的完全二叉树：

1
2
3
4
5

        1 (下标0)
       /    \
  3(1)      2(2)
  /  \      /   \
7(3) 9(4) 8(5)  4(6)

1）求父节点

公式：父下标 = (i - 1) / 2

比如：

  • 节点 7 的下标 i=3
    父下标 = (3-1)/2 = 2/2 = 1 → 父是节点 3

  • 节点 2 的下标 i=2
    父下标 = (2-1)/2 = 1/2 = 0 → 父是节点 1

2）求左孩子

公式：左孩子下标 = 2*i + 1

比如：

  • 节点 1 的下标 i=0
    左孩子 = 2*0+1 = 1 → 是 3

3）求右孩子

公式：右孩子下标 = 2*i + 2

比如：

  • 节点 1 的下标 i=0
    右孩子 = 2*0+2 = 2 → 是 2

4）求根节点

公式：父节点下标 = (i - 1) / 2

比如：

  • 节点 1 的下标 i=0
    父节点 = (0 - 1) / 2 = -1
    → 说明根节点没有父节点

三、时间复杂度

操作 时间复杂度
插入元素 O(log n)
删除堆顶 O(log n)
查看堆顶 O(1)

四、最小堆示意图（最常用）

1
2
3
4
5
6
7

          1
        /   \
       3     2
      / \   / \
     7  9  8   4

数组：[1, 3, 2, 7, 9, 8, 4]
  • 父 ≤ 子
  • 堆顶（第一个元素）最小

五、最大堆示意图（对照看）

1
2
3
4
5
6
7

          9
        /   \
       7     8
      / \   / \
     4  3  2   1

数组：[9, 7, 8, 4, 3, 2, 1]
  • 父 ≥ 子
  • 堆顶最大

六、核心操作逻辑

  1. 插入（向上调整 heapifyUp）
  • 把新元素放到数组最后
  • 不断和父节点比较
  • 比父小（最小堆）就交换，直到符合堆规则
  1. 删除堆顶（向下调整 heapifyDown）
  • 把最后一个元素移到堆顶
  • 不断和左右孩子比较
  • 和更小的孩子（最小堆）交换，直到符合堆规则

七、应用场景

  • 优先级队列（Java PriorityQueue）
  • TopK 问题（取最大/最小前 K 个）
  • 堆排序
  • 任务调度、定时器

八、重要说明

  • Java 工具类 PriorityQueue 底层就是最小堆
  • 最大堆可以通过反转比较规则实现
  • 堆的所有操作都依赖 完全二叉树结构 + 数组下标公式

九、Java 实现（最小堆）

最小堆 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101

public class MinHeap {
    private int[] heap;   // 存储堆的数组
    private int size;     // 当前堆里元素个数
    private int capacity; // 堆最大容量

    // 构造方法：初始化堆容量
    public MinHeap(int capacity) {
        this.capacity = capacity;
        this.heap = new int[capacity];
        this.size = 0;
    }

    // ==================== 插入元素 ====================
    public void insert(int val) {
        if (size == capacity)
            throw new IllegalStateException("堆已满");

        heap[size] = val;      // 新元素放最后
        heapifyUp(size);       // 向上调整
        size++;                // 元素个数+1
    }

    // ==================== 删除堆顶（最小值） ====================
    public int extractMin() {
        if (size == 0)
            throw new IllegalStateException("堆为空");

        int min = heap[0];             // 记录堆顶最小值
        heap[0] = heap[--size];        // 最后一个元素移到堆顶
        heapifyDown(0);               // 向下调整
        return min;
    }

    // ==================== 查看堆顶（不删除） ====================
    public int peek() {
        if (size == 0)
            throw new IllegalStateException("堆为空");
        return heap[0];
    }

    // ==================== 向上调整（插入用） ====================
    // 子节点比父小，就往上交换
    private void heapifyUp(int index) {
        // 不是根节点就循环
        while (index > 0) {
            int parent = (index - 1) / 2; // 找父节点

            // 子 >= 父，符合最小堆，不用继续调整
            if (heap[index] >= heap[parent])
                break;

            swap(index, parent); // 交换
            index = parent;      // 继续向上检查
        }
    }

    // ==================== 向下调整（删除堆顶用） ====================
    // 父节点比孩子大，就往下交换
    private void heapifyDown(int index) {
        while (true) {
            int left = 2 * index + 1;   // 左孩子
            int right = 2 * index + 2;  // 右孩子
            int smallest = index;       // 最小值下标，默认自己

            // 左孩子更小
            if (left < size && heap[left] < heap[smallest])
                smallest = left;

            // 右孩子更小
            if (right < size && heap[right] < heap[smallest])
                smallest = right;

            // 自己最小，不用调整
            if (smallest == index)
                break;

            swap(index, smallest); // 交换
            index = smallest;      // 继续向下检查
        }
    }

    // ==================== 交换工具方法 ====================
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // 测试
    public static void main(String[] args) {
        MinHeap heap = new MinHeap(10);
        heap.insert(5);
        heap.insert(3);
        heap.insert(7);
        heap.insert(2);
        heap.insert(4);

        System.out.println(heap.extractMin()); // 输出 2
        System.out.println(heap.peek());       // 输出 3
    }
}

6.5 前缀树（Trie）

一、核心概念

前缀树，又称字典树，是一种多叉树数据结构，专门高效处理字符串前缀检索、批量单词匹配问题。

核心特点：

  1. 根节点为空，节点本身不存储字符；
  2. 字符记录在节点与节点的边上；
  3. 单个节点最多可拥有多个子节点（小写字母场景为26个）；
  4. 从根节点到某一节点的完整路径，对应一个字符串/单词；
  5. 节点自带 isEnd 标记，区分「普通前缀节点」和「完整单词结尾节点」；
  6. 拥有相同前缀的单词共享公共节点，大幅节省存储空间。

二、时间复杂度

设字符串长度为 (L)

操作 时间复杂度
插入单词 (O(L))
完整查询 (O(L))
前缀匹配 (O(L))

优势：执行效率与单词总数量无关，仅由字符串长度决定，适合海量字符串前缀检索。

三、底层结构 + 标准数据结构示意图

  1. 这个整体 → 就叫前缀树（Trie）
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

root
 ↓
 a
 ↓
 p
 ↓
 p (isEnd=true)
 ↓
 l
 ↓
 e (isEnd=true)
  1. 每个字母 → 就是一个节点
  • a → 节点
  • p → 节点
  • p → 节点
  • l → 节点
  • e → 节点
  1. 单个节点结构

前缀树每一个节点固定组成：

  • 子节点数组：children[26]，对应小写字母 a~z，存放下级节点引用；
  • 结束标记：boolean isEnd，标记当前位置是否为一个单词的末尾。
1
2
3

TrieNode节点
├─ children[26]  // 指向26个字母对应的子节点
└─ isEnd 标记    // 标记是否为完整单词结尾
  1. 基础结构示例（存入单词：cat）
1
2
3
4

root （根节点）
 └─ c节点
      └─ a节点
           └─ t节点 [isEnd = true]
  1. 公共前缀共享结构（存入：app、apple）

完美体现前缀树共享前缀、节约空间的核心特性：

1
2
3
4
5
6

root （根节点）
 └─ a节点
    └─ p节点
       └─ p节点 [isEnd=true]      // 单词 app 在此结束
          └─ l节点
             └─ e节点 [isEnd=true]// 单词 apple 在此结束
  1. 分叉前缀结构（存入：cat、car）

同一个前缀下分出不同后缀，是多叉树典型形态：

1
2
3
4
5
6
7
8

        root
         │
         c
         │
         a
       /   \
      t     r
  (end)   (end)

四、典型应用场景

  1. 输入法联想、关键词自动补全；
  2. 词典单词检索、模糊前缀查询；
  3. 平台敏感词批量过滤；
  4. 网络路由最长前缀匹配；
  5. 海量字符串去重、前缀分组统计。

五、核心设计思想

  1. 小写英文字典树：固定开辟 26 个空间，一一对应 a~z，访问效率极高；
  2. 依靠数组下标映射字符：c - 'a'，快速定位子节点位置；
  3. 依靠 isEnd 字段，区分「中间前缀」和「完整单词」；
  4. 公共前缀只创建一份节点，避免重复存储冗余字符。

六、易混点总结

  1. search(word)：精准匹配完整单词，需要路径存在 + 末尾isEnd=true；
  2. startsWith(prefix)：前缀匹配，只要完整走完前缀路径即可，无需结尾标记；
  3. 根节点无字符、无含义，仅作为遍历起点；
  4. 字符存于边，节点只负责管理子节点与结束标记。

七、扩展优化

  1. 纯小写英文场景：使用 TrieNode[26] 数组实现，速度快、内存占用小；
  2. 复杂字符集（大写、数字、中文、Unicode）： 替换数组为 HashMap<Character, TrieNode>，动态按需创建子节点，避免空间浪费。

八、Java 代码实现

前缀树 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

public class Trie {
    // 内部节点类：定义前缀树节点结构
    private static class TrieNode {
        TrieNode[] children = new TrieNode[26]; // 对应 a-z 26个小写字母
        boolean isEnd = false;                 // 标记当前节点是否为单词结尾
    }

    // 全局唯一根节点
    private final TrieNode root = new TrieNode();

    // 插入单词到前缀树
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a'; // 字符转为0~25下标
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index]; // 指针下移
        }
        node.isEnd = true; // 标记单词结束
    }

    // 精确查询：是否存在完整单词
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    // 前缀匹配：是否存在指定前缀
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    // 公共抽取方法：遍历前缀，返回最终到达的节点
    private TrieNode searchPrefix(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return null; // 路径断裂，前缀不存在
            }
            node = node.children[index];
        }
        return node;
    }

    // 测试运行
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("app");
        trie.insert("apple");

        System.out.println(trie.search("app"));      // true
        System.out.println(trie.search("appl"));     // false
        System.out.println(trie.startsWith("app"));   // true
        System.out.println(trie.startsWith("bat"));  // false
    }
}

7. 图（Graph）

一、核心概念

图是一种非线性数据结构，用来描述多个实体之间的多对多复杂关系。 两大基础组成：

  1. 顶点（Vertex）：具体实体、节点，就是图里的一个个「节点」
  2. 边（Edge）：两个顶点之间的连接关系，就是节点和节点之间的连接

二、基础分类

  1. 按连接方向
  • 无向图：顶点之间双向连通，无方向限制
  • 有向图：顶点之间单向连通，有明确指向
  1. 按权重大小
  • 无权图：边只有连接关系，无数值大小
  • 加权图：每条边附带权重（距离、成本、耗时等）

三、基础结构图示

  1. 无向图示意
1
2
3

  0 —— 1
  |
  4 —— 3

顶点互相双向连通。

  1. 有向图示意
1
2

  0 → 1
  2 → 3

只能按箭头单向访问。

四、两种核心存储方式

先明确两个最基础概念：

  • V：顶点总数（图里的每一个点）
  • E：边总数（点与点之间的连线）

我们用下面这张 4个顶点、4条边 的图来举例：

1
2
3

  0 ---- 1
  |      |
  2 ---- 3

顶点 V = 4 边 E = 4

  1. 邻接矩阵（二维数组表格）

结构图示

1
2
3
4
5

      0  1  2  3
0   [ 0  1  1  0 ]
1   [ 1  0  0  1 ]
2   [ 1  0  0  1 ]
3   [ 0  1  1  0 ]

核心解释

  • 有 V 个顶点 → 生成 V × V 正方形表格
  • 表格格子：
    • 1 = 两点相连
    • 0 = 不相连
  • 不管有没有连线，所有位置都占满空间
  • 空间复杂度：O(V²) 4 个顶点 → 4×4 = 16 个位置

特点

  • 优点：瞬间判断两点是否相连
  • 缺点：费空间
  • 适合：点少、连线多 → 稠密图
  1. 邻接表（每个点一个邻居列表）

结构图示

1
2
3
4

顶点 0 的邻居：[1, 2]
顶点 1 的邻居：[0, 3]
顶点 2 的邻居：[0, 3]
顶点 3 的邻居：[1, 2]

核心解释

  • 不搞正方形表格
  • 每个顶点 = 一个列表
  • 列表里只存真实相连的邻居
  • 空间只跟：顶点数量 V + 边数量 E 有关
  • 空间复杂度：O(V + E) 4 个顶点 + 4 条边 → O(4+4)

特点

  • 优点：超级省空间、遍历邻居快
  • 缺点：判断两点是否相连稍慢
  • 适合：点多、连线少 → 稀疏图 （工程 90% 都用它）

最终对比表

存储方式 空间复杂度 核心特点 & 适用场景
邻接矩阵 (O(V^2)) 正方形表格，占满空间；稠密图，快速查两点是否连通
邻接表 (O(V+E)) 每个点一个邻居列表，只存真实连线；稀疏图，省空间、遍历快

五、常用操作复杂度对比

操作 邻接矩阵 邻接表
添加边 (O(1)) (O(1))
删除边 (O(1)) (O(E))
遍历邻居 (O(V)) (O(E))

六、核心遍历方式

参考示例图

1
2
3

  0 ---- 1
  |      |
  2 ---- 3

顶点关系：
0邻居：1、2
1邻居：0、3
2邻居：0、3
3邻居：1、2

  1. BFS 广度优先遍历
  • 逻辑：以起点为中心，先把自己所有直接邻居全部访问完，再去访问「邻居的邻居」，由近到远、一层一层向外扩散。
  • 层级划分（很好理解）：
    第0层：起始顶点（如：0）
    第1层：和起点直接相连的相邻点（如：1、2）
    第2层：隔一层的间接点（如：3）
  • 行走顺序举例（从顶点 0 开始）：
    先访问起点 0 → 再统一访问同层直接邻居 1、2 → 最后访问下一层 3
    访问顺序：0 → 1 → 2 → 3
  • 底层依赖：队列
  • 适用：最短路径、层序搜索、范围扩散查找
  1. DFS 深度优先遍历
  • 逻辑：不按层走，随便选一条分支，一条路直接走到最深处； 这条路走到头、没有新节点时，再回头回溯，依次走之前没走的其他分叉路口。
  • 行走顺序举例（从顶点 0 开始）：
    选一条路一直往下钻：0 → 1 → 3
    这条路走到底没新点了，回头回溯，再走剩下分支：走到 2
    访问顺序：0 → 1 → 3 → 2
  • 底层依赖：递归 / 栈
  • 适用：连通性判断、全路径搜索、拓扑排序

七、典型应用场景

  1. 社交网络好友关系、关注链
  2. 地图导航、路径规划、最短路线
  3. 项目依赖、任务调度、拓扑排序
  4. 网络拓扑、知识图谱、关系图谱

八、实现说明

  1. 邻接表：日常开发、算法刷题最常用，用 Map + List 动态存储邻居节点，节省空间；
  2. 邻接矩阵：适合顶点数量固定、需要频繁判断两点连通性的场景；
  3. 无向图添加边需要双向赋值，有向图只需要单向赋值。

九、Java 代码实现

图 完整代码

9.1 邻接表实现（主流）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

import java.util.*;

public class Graph {
    // 邻接表：key=顶点，value=该顶点的所有邻居
    private Map<Integer, List<Integer>> adj = new HashMap<>();

    // 初始化所有顶点
    public Graph(int numVertices) {
        for (int i = 0; i < numVertices; i++) {
            adj.put(i, new LinkedList<>());
        }
    }

    // 无向图 添加双向边
    public void addEdgeUndirected(int src, int dest) {
        adj.get(src).add(dest);
        adj.get(dest).add(src);
    }

    // 有向图 添加单向边
    public void addEdgeDirected(int src, int dest) {
        adj.get(src).add(dest);
    }

    // BFS 广度优先遍历（队列实现）
    public void bfs(int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited.add(start);

        System.out.print("BFS遍历：");
        while (!queue.isEmpty()) {
            int v = queue.poll();
            System.out.print(v + " ");
            // 遍历当前顶点所有邻居
            for (int neighbor : adj.get(v)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        System.out.println();
    }

    // DFS 深度优先遍历（递归）
    public void dfs(int start) {
        Set<Integer> visited = new HashSet<>();
        System.out.print("DFS遍历：");
        dfsRecursive(start, visited);
        System.out.println();
    }

    private void dfsRecursive(int v, Set<Integer> visited) {
        visited.add(v);
        System.out.print(v + " ");
        // 深度递归访问每一个未访问邻居
        for (int neighbor : adj.get(v)) {
            if (!visited.contains(neighbor)) {
                dfsRecursive(neighbor, visited);
            }
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph(5);
        g.addEdgeUndirected(0, 1);
        g.addEdgeUndirected(0, 4);
        g.addEdgeUndirected(1, 3);
        g.addEdgeDirected(2, 3);

        g.bfs(0);
        g.dfs(0);
    }
}

代码解释

先统一用这张图理解

1
2
3
4
5

0 —— 1
|     |
4     3
     /
    2 （单向指向3）

顶点：0,1,2,3,4

  1. 先讲：邻接表长啥样？
1

Map<Integer, List<Integer>> adj

意思：
key = 顶点
value = 这个顶点的邻居列表

一开始是空的：

1
2
3
4
5

0: []
1: []
2: []
3: []
4: []
  1. addEdgeUndirected 无向边（双向互通）
1
2
3
4

public void addEdgeUndirected(int src, int dest) {
    adj.get(src).add(dest);   // src 里加 dest
    adj.get(dest).add(src);   // dest 里加 src
}

人话：
A 能到 B，B 也能到 A → 互相加邻居

举例：添加 0 — 1

1
2

adj.get(0).add(1);   →  0的邻居：[1]
adj.get(1).add(0);   →  1的邻居：[0]

结果变成：

1
2

0: [1]
1: [0]

再加 0 — 4

1
2

0: [1,4]
4: [0]

再加 1 —3

1
2

1: [0,3]
3: [1]
  1. addEdgeDirected 有向边（单向走）
1
2
3

public void addEdgeDirected(int src, int dest) {
    adj.get(src).add(dest);   // 只加一次！
}

人话：
A 能到 B，但 B 不能到 A → 只给 A 加邻居

举例：2 → 3

1

adj.get(2).add(3);

结果：

1
2

2: [3]
3: 不受影响！
  1. 最终邻接表长这样
1
2
3
4
5

0: [1,4]
1: [0,3]
2: [3]
3: [1]
4: [0]
  1. 最懵的 BFS：队列里谁放的数据？

（1）开头两行

1
2

queue.offer(start);   // start=0
visited.add(start);

意思：
先把起点 0 放进队列！
先把起点 0 标记已访问！

（2）进入循环

1
2
3

while (!queue.isEmpty()) {
    int v = queue.poll();  // 取出 0
    System.out.print(v);

（3）遍历 0 的邻居：1、4

1
2
3
4
5
6

for (int neighbor : adj.get(0)) {
    if (!visited.contains(neighbor)) {
        visited.add(neighbor);
        queue.offer(neighbor);  <-- 这里往队列加数据！
    }
}

这里做了什么？

  • 邻居 1 没访问 → 加入队列
  • 邻居 4 没访问 → 加入队列

队列现在变成：[1,4]

（4）下一轮循环

1

v = queue.poll(); // 取出 1

遍历 1 的邻居：0（已访问）、3
→ 3 没访问 → 加入队列

队列现在：[4,3]

（5）再下一轮

1

v = queue.poll(); // 取出4

4 的邻居只有 0（已访问）
→ 不加人

队列现在：[3]

（6）再下一轮

1

v = queue.pool(); // 取出3

3 的邻居 1（已访问）
→ 不加人

队列空 → 结束！

  1. 最关键的疑问

谁向 queue 里添加数据了？

答案：

1

queue.offer(neighbor);

遍历邻居时，把没访问过的节点加入队列！

为什么开头可以直接 poll？

1

queue.offer(start);

开头第一行就把起点放进去了！队列一开始就不为空！

  1. 整段 BFS 人话总结

1）. 把起点放进队列
2）. 取出一个点
3）. 把它所有没访问的邻居扔进队列
4）. 重复直到队列为空

这就是 一层一层遍历 的核心！

  1. DFS 简单说
1

dfsRecursive(neighbor, visited);
  • 选中一个邻居
  • 直接钻进去
  • 钻到底再回来
  • 就是“一条路走到黑”

9.2 邻接矩阵实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

import java.util.Arrays;

public class GraphMatrix {
    private int[][] matrix;     // 邻接矩阵
    private int numVertices;    // 顶点数量

    public GraphMatrix(int numVertices) {
        this.numVertices = numVertices;
        matrix = new int[numVertices][numVertices];
    }

    // 无向图 双向赋值
    public void addEdgeUndirected(int i, int j) {
        matrix[i][j] = 1;
        matrix[j][i] = 1;
    }

    // 有向图 单向赋值
    public void addEdgeDirected(int i, int j) {
        matrix[i][j] = 1;
    }

    public static void main(String[] args) {
        GraphMatrix g = new GraphMatrix(4);
        g.addEdgeUndirected(0, 1);
        g.addEdgeUndirected(0, 2);
        g.addEdgeDirected(1, 3);

        // 打印邻接矩阵
        for (int[] row : g.matrix) {
            System.out.println(Arrays.toString(row));
        }
    }
}

二、基础算法

1. 二分查找

一、核心原理

二分查找，是针对有序数组的高效查找算法。
核心思想：
在固定区间内，每次取中间元素对比，排除一半无效区间，不断缩小区间范围，快速定位目标值。

二、前置必备条件

  1. 数组必须 有序（升序/降序）
  2. 支持下标随机访问（数组结构）

三、二分查找结构示意图

示例有序数组：

1
2

下标：  0    1    2    3    4    5     6
数值：[ 1 ,  3 ,  5 ,  7 ,  9 , 11 ,  13 ]

查找目标：target = 7

第一轮区间

1
2
3
4
5

left=0                right=6
      ↓                ↓
[ 1 , 3 , 5 , 7 , 9 , 11 , 13 ]
            ↑
           mid

对比中间值，直接命中目标。

通用查找逻辑示意

1
2
3
4
5
6
7
8
9

原始大范围
——————————————————
     ↓
砍掉一半无效范围
——————————
     ↓
再砍掉一半
—————
直到找到目标 / 区间消失

四、执行流程

  1. 定义左边界 left、右边界 right，锁定查找区间；
  2. 计算中间位置 mid；
  3. 三种情况：
    • arr[mid] == target：查找成功，返回下标；
    • arr[mid] < target：目标在右侧，左边界收缩；
    • arr[mid] > target：目标在左侧，右边界收缩；
  4. 循环缩小区间，直到找到目标 或 区间遍历结束。

五、复杂度

项目 复杂度
时间 O(log n)
空间（迭代） O(1)
空间（递归） O(log n)

六、常见面试变体

  • 查找第一个等于 target 的位置
  • 查找最后一个等于 target 的位置
  • 查找第一个大于等于 target 的位置
  • 查找最后一个小于等于 target 的位置
常见面试变体

前置统一

1

int mid = left + (right - left) / 2;

1. 变体一：查找「第一个等于 target」的位置

需求： 有重复元素，要最左边那个目标。

思路

  1. 普通二分：arr[mid] == target 直接 return
  2. 现在：找到 target 不停止，继续向左找，看左边还有没有相同的
  3. 收缩右边界：right = mid - 1
  4. 循环结束后，单独校验 left 位置是不是 target

核心代码

1
2
3
4
5
6
7

if (arr[mid] == target) {
    right = mid - 1; // 往左缩，找更靠前的
} else if (arr[mid] < target) {
    left = mid + 1;
} else {
    right = mid - 1;
}

记忆：等于就往左压

2. 变体二：查找「最后一个等于 target」的位置

需求： 有重复元素，要最右边那个目标。

思路

  1. 找到 target 不停止
  2. 继续向右找，看右边还有没有相同
  3. 收缩左边界：left = mid + 1

核心代码

1
2
3
4
5
6
7

if (arr[mid] == target) {
    left = mid + 1; // 往右缩，找更靠后的
} else if (arr[mid] < target) {
    left = mid + 1;
} else {
    right = mid - 1;
}

记忆：等于就往右压

3. 变体三：查找「第一个 大于等于 target」的位置

别名：左边界二分 场景：找不到target，就找比它大、离它最近的第一个数

思路

  1. arr[mid] < target → 太小，左边界右移
  2. arr[mid] >= target → 符合条件，尝试往左再找一个更小的满足点
  3. 最终 left 就是答案

核心代码

1
2
3
4
5

if (arr[mid] >= target) {
    right = mid - 1;
} else {
    left = mid + 1;
}

记忆：大于等于，就往左收紧

4. 变体四：查找「最后一个 小于等于 target」的位置

别名：右边界二分
场景：找不到target，找比它小、离它最近的最后一个数

思路

  1. arr[mid] > target → 太大，右边界左移
  2. arr[mid] <= target → 符合条件，往右再找更大的满足点

核心代码

1
2
3
4
5

if (arr[mid] <= target) {
    left = mid + 1;
} else {
    right = mid - 1;
}

记忆：小于等于，就往右收紧

超级总结口诀

  1. 找第一个等于：命中往左压
  2. 找最后一个等于：命中往右压
  3. 找大于等于(左边界)：>= 就左缩
  4. 找小于等于(右边界)：<= 就右缩

补充一句话通用逻辑

  • 要靠左的答案：只要满足条件，就压缩右边界 right = mid - 1
  • 要靠右的答案：只要满足条件，就压缩左边界 left = mid + 1

七、Java 实现

二分查找 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

public class BinarySearch {
    // 迭代版本：日常推荐，常数级空间、无栈溢出风险
    public static int binarySearch(int[] arr, int target) {
        // 左边界：起始下标
        int left = 0;
        // 右边界：数组最后一个元素下标
        int right = arr.length - 1;

        // 区间合法时循环查找
        while (left <= right) {
            // 安全计算中间下标，避免 left+right 数值溢出
            int mid = left + (right - left) / 2;

            // 1. 中间值等于目标，直接返回下标
            if (arr[mid] == target) {
                return mid;
            }
            // 2. 中间值小于目标 → 目标在右半区，左边界右移
            else if (arr[mid] < target) {
                left = mid + 1;
            }
            // 3. 中间值大于目标 → 目标在左半区，右边界左移
            else {
                right = mid - 1;
            }
        }
        // 查找完毕，无目标元素
        return -1;
    }

    // 递归版本：逻辑直观，适合理解原理
    public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
        // 区间交叉，查找失败
        if (left > right) {
            return -1;
        }
        // 计算中间下标
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            // 去右半区递归查找
            return binarySearchRecursive(arr, target, mid + 1, right);
        } else {
            // 去左半区递归查找
            return binarySearchRecursive(arr, target, left, mid - 1);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        System.out.println(binarySearch(arr, 7));  // 元素存在，返回下标 3
        System.out.println(binarySearch(arr, 6));  // 元素不存在，返回 -1
    }
}

2. 排序算法

一、排序算法分类

排序类别 包含算法 核心特点
交换类排序（互相交换元素） 冒泡排序、快速排序 靠元素交换调整位置，思路直观
选择类排序（选最值放对应位置） 选择排序、堆排序 先找最小/最大值，再放到目标位置
插入类排序（往有序区间插入） 插入排序、希尔排序 逐步构建有序区间，将元素插入对应位置
合并分治类（拆分+合并） 归并排序 分治思想，先拆分再合并，稳定性强
非比较类排序（不比较元素大小） 计数排序、基数排序、桶排序 依赖数据范围，速度极快，有适用限制

二、逐个算法详解

2.1 交换类排序

2.1.1 冒泡排序
一、核心原理

重复遍历数组，每次比较相邻两个元素，把较大的元素“冒泡”到数组末尾；
遍历一次，就确定一个最大元素的最终位置，重复直到整个数组有序。
核心：相邻对比、逐步冒泡，小的往前移，大的往后沉。

二、流程示意图
1
2
3
4
5

原数组：[5, 3, 8, 4, 2]
第1轮遍历（冒泡出最大数8）：[3, 5, 4, 2, 8]
第2轮遍历（冒泡出第二大数5）：[3, 4, 2, 5, 8]
第3轮遍历（冒泡出第三大数4）：[3, 2, 4, 5, 8]
第4轮遍历（冒泡出第四大数3）：[2, 3, 4, 5, 8]
三、核心特点
  • 逻辑最简单，上手最快
  • 原地排序，不需要额外空间
  • 稳定排序：相等元素相对顺序不变
  • 效率低，适合小规模数据
四、复杂度
项目 平均 最坏 最好（优化后）
时间复杂度 (O(n^2)) (O(n^2)) (O(n))（数组已有序）
空间复杂度 (O(1)) (O(1)) (O(1))
五、Java 实现
冒泡排序 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

import java.util.Arrays;

public class BubbleSort {

    /**
     * 冒泡排序入口
     * @param arr 待排序数组
     */
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        // 外层循环：控制排序轮数，n个元素需要n-1轮（最后1个元素天然有序）
        for (int i = 0; i < n - 1; i++) {
            // 标记：是否发生交换，优化已有序数组
            boolean swapped = false;

            // 内层循环：遍历未排序区间，相邻元素对比交换
            // 每轮结束，最大元素已冒泡到末尾，无需再遍历
            for (int j = 0; j < n - 1 - i; j++) {
                // 前一个元素 > 后一个元素，交换（冒泡）
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    swapped = true; // 标记发生交换
                }
            }

            // 优化：如果一轮没发生交换，说明数组已有序，直接退出
            if (!swapped) {
                break;
            }
        }
    }

    // 数组交换两个下标元素
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr)); // [2, 3, 4, 5, 8]
    }
}
2.1.2 快速排序（面试重点、效率最高）
一、核心原理

采用 分治思想：

  1. 在数组中选一个元素作为「基准值 pivot」；
  2. 把数组分区：小于基准放左边，大于等于基准放右边；
  3. 左右两个子区间，递归重复分区、排序；
  4. 层层递归拆分，最终整个数组有序。
二、流程示意图
1
2
3
4
5

原数组：[10, 7, 8, 9, 1, 5]
选基准：5
分区后：[1 | 5 | 10,7,8,9]
递归左区间、递归右区间
最终有序：[1, 5, 7, 8, 9, 10]
三、核心特点
  • 原地排序，不需要额外大量空间
  • 不稳定排序：相等元素相对顺序可能改变
  • 日常工程、刷题综合效率最高
四、复杂度
项目 平均 最坏
时间复杂度 (O(n\log n)) (O(n^2))
空间复杂度 (O(\log n)) (O(n))
五、Java 实现
快速排序 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

import java.util.Arrays;

public class QuickSort {

    /**
     * 快速排序入口
     * @param arr 待排序数组
     * @param low 左边界下标
     * @param high 右边界下标
     */
    public static void quickSort(int[] arr, int low, int high) {
        // 区间合法，才有必要排序
        if (low < high) {
            // 分区操作，拿到基准值最终下标
            int pivotIndex = partition(arr, low, high);
            // 递归排序 基准左侧区间
            quickSort(arr, low, pivotIndex - 1);
            // 递归排序 基准右侧区间
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    /**
     * 分区函数：划分左右区域
     * 规则：小于基准放左边，大于等于基准放右边
     * @return 基准元素最终位置下标
     */
    private static int partition(int[] arr, int low, int high) {
        // 选取最右侧元素作为基准值
        int pivot = arr[high];
        // i：小于基准区域的右边界
        int i = low - 1;

        // j 遍历整个区间，逐个和基准对比
        for (int j = low; j < high; j++) {
            // 当前元素小于基准，划入左区域
            if (arr[j] < pivot) {
                i++;
                // 交换，把小元素换到左侧区域
                swap(arr, i, j);
            }
        }
        // 把基准值放到左右区域中间固定位置
        swap(arr, i + 1, high);
        // 返回基准下标，作为下次递归分割点
        return i + 1;
    }

    // 数组交换两个下标元素
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        // 初始边界：0 ~ 数组最后一位
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr)); // [1, 5, 7, 8, 9, 10]
    }
}
六、补充知识点
  1. 最坏场景：数组本身有序、固定选最左/最右当基准，退化遍历 (O(n^2))
  2. 常用优化策略：
  • 三数取中：从左端、右端、中间选中间值当基准
  • 小数组区间改用插入排序，减少递归开销
  • 尾递归优化，降低栈空间消耗

2.2 选择类排序

2.2.1 选择排序（简单易记，比冒泡高效）
一、核心原理

每次从未排序区间，找到最小（或最大）的元素，放到未排序区间的起始位置；
重复操作，逐步缩小未排序区间，直到整个数组有序。
核心：选最值、放首位，不频繁交换，只在找到最值后交换一次。

二、流程示意图
1
2
3
4
5

原数组：[5, 3, 8, 4, 2]
第1轮：找到最小值2，和首位5交换 → [2, 3, 8, 4, 5]
第2轮：找到剩余最小值3，位置不变 → [2, 3, 8, 4, 5]
第3轮：找到剩余最小值4，和8交换 → [2, 3, 4, 8, 5]
第4轮：找到剩余最小值5，和8交换 → [2, 3, 4, 5, 8]
三、核心特点
  • 逻辑简单，交换次数少（比冒泡排序高效）
  • 原地排序，不需要额外空间
  • 不稳定排序：相等元素相对顺序可能改变
  • 效率低，适合小规模数据
四、复杂度
项目 平均 最坏 最好
时间复杂度 (O(n^2)) (O(n^2)) (O(n^2))
空间复杂度 (O(1)) (O(1)) (O(1))
五、Java 实现
选择排序 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

import java.util.Arrays;

public class SelectionSort {

    /**
     * 选择排序入口
     * @param arr 待排序数组
     */
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        // 外层循环：控制未排序区间的起始位置（0 ~ n-2）
        // 最后一个元素天然有序，无需处理
        for (int i = 0; i < n - 1; i++) {
            // 假设当前未排序区间的第一个元素是最小值
            int minIndex = i;

            // 内层循环：遍历未排序区间，找到真正的最小值下标
            for (int j = i + 1; j < n; j++) {
                // 找到更小的元素，更新最小值下标
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // 把最小值交换到未排序区间的起始位置
            if (minIndex != i) { // 优化：如果本身就是最小值，不交换
                swap(arr, i, minIndex);
            }
        }
    }

    // 数组交换两个下标元素
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr)); // [2, 3, 4, 5, 8]
    }
}
2.2.2 堆排序（利用堆结构，高效排序）
一、核心原理

利用前面学过的 堆数据结构（大顶堆），核心分两步：

  1. 构建大顶堆：将数组转换成大顶堆（父节点 > 子节点），堆顶是整个数组的最大值；
  2. 堆顶交换+堆调整：将堆顶（最大值）和数组末尾元素交换，然后调整剩余元素为大顶堆；
  3. 重复步骤2，逐步将最大值、第二大值、第三大值…放到对应位置，最终有序。
二、流程示意图
1
2
3
4
5
6

原数组：[4, 6, 8, 5, 9]
1. 构建大顶堆：[9, 6, 8, 5, 4]（堆顶9是最大值）
2. 堆顶9和末尾4交换 → [4, 6, 8, 5, 9]，调整前4个元素为大顶堆 → [8, 6, 4, 5, 9]
3. 堆顶8和倒数第二个5交换 → [5, 6, 4, 8, 9]，调整前3个元素为大顶堆 → [6, 5, 4, 8, 9]
4. 堆顶6和倒数第三个4交换 → [4, 5, 6, 8, 9]，调整前2个元素为大顶堆 → [5, 4, 6, 8, 9]
5. 堆顶5和倒数第四个4交换 → [4, 5, 6, 8, 9]，排序完成
三、核心特点
  • 原地排序，不需要额外大量空间
  • 不稳定排序：相等元素相对顺序可能改变
  • 效率高，时间复杂度稳定，适合大规模数据
四、复杂度
项目 平均 最坏 最好
时间复杂度 (O(n\log n)) (O(n\log n)) (O(n\log n))
空间复杂度 (O(1)) (O(1)) (O(1))
五、Java 实现
堆排序 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

import java.util.Arrays;

public class HeapSort {

    /**
     * 堆排序入口
     * @param arr 待排序数组
     */
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // 1. 构建大顶堆（从最后一个非叶子节点开始调整）
        // 最后一个非叶子节点下标：n/2 - 1
        for (int i = n / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, n, i);
        }

        // 2. 堆顶交换 + 堆调整（循环n-1次）
        for (int i = n - 1; i > 0; i--) {
            // 把堆顶（最大值）和当前未排序区间末尾元素交换
            swap(arr, 0, i);
            // 调整剩余元素为大顶堆（只调整堆顶，范围缩小到0~i-1）
            adjustHeap(arr, i, 0);
        }
    }

    /**
     * 调整堆结构，使其成为大顶堆
     * @param arr 待调整数组
     * @param heapSize 堆的大小（当前未排序区间长度）
     * @param parent 父节点下标（要调整的节点）
     */
    private static void adjustHeap(int[] arr, int heapSize, int parent) {
        // 左子节点下标 = 2*parent + 1
        int leftChild = 2 * parent + 1;
        // 右子节点下标 = 2*parent + 2
        int rightChild = 2 * parent + 2;
        // 假设父节点是最大值
        int maxIndex = parent;

        // 对比左子节点，找到更大值
        if (leftChild < heapSize && arr[leftChild] > arr[maxIndex]) {
            maxIndex = leftChild;
        }
        // 对比右子节点，找到更大值
        if (rightChild < heapSize && arr[rightChild] > arr[maxIndex]) {
            maxIndex = rightChild;
        }

        // 如果最大值不是父节点，交换，并递归调整子堆
        if (maxIndex != parent) {
            swap(arr, parent, maxIndex);
            // 递归调整被交换的子节点所在的子堆
            adjustHeap(arr, heapSize, maxIndex);
        }
    }

    // 数组交换两个下标元素
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {4, 6, 8, 5, 9};
        heapSort(arr);
        System.out.println(Arrays.toString(arr)); // [4, 5, 6, 8, 9]
    }
}

2.3 插入类排序

2.3.1 插入排序（简单、接近日常排序习惯）
一、核心原理

逐步构建有序区间：

  1. 假设数组第1个元素是有序区间；
  2. 从第2个元素开始，逐个将元素插入到前面的有序区间中，找到合适的位置；
  3. 重复操作，直到所有元素都插入有序区间，数组整体有序。

核心：像整理扑克牌一样，把新元素插入到已经排好序的牌堆里。

二、流程示意图
1
2
3
4
5

原数组：[5, 3, 8, 4, 2]
第1步：有序区间[5]，插入3 → [3, 5, 8, 4, 2]
第2步：有序区间[3,5]，插入8 → [3, 5, 8, 4, 2]（位置不变）
第3步：有序区间[3,5,8]，插入4 → [3, 4, 5, 8, 2]
第4步：有序区间[3,4,5,8]，插入2 → [2, 3, 4, 5, 8]
三、核心特点
  • 逻辑简单，接近日常手动排序习惯
  • 原地排序，不需要额外空间
  • 稳定排序：相等元素相对顺序不变
  • 效率低，适合小规模数据、接近有序的数组
四、复杂度
项目 平均 最坏 最好（数组有序）
时间复杂度 (O(n^2)) (O(n^2)) (O(n))
空间复杂度 (O(1)) (O(1)) (O(1))
五、Java 实现
插入排序 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

import java.util.Arrays;

public class InsertionSort {

    /**
     * 插入排序入口
     * @param arr 待排序数组
     */
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        // 外层循环：从第2个元素开始（下标1），逐个插入有序区间
        for (int i = 1; i < n; i++) {
            // 要插入的目标元素
            int target = arr[i];
            // 有序区间的最后一个元素下标（初始为i-1）
            int j = i - 1;

            // 内层循环：在有序区间中找到目标元素的插入位置
            // 当j >=0 且 有序区间元素 > 目标元素，元素后移
            while (j >= 0 && arr[j] > target) {
                arr[j + 1] = arr[j]; // 元素后移，腾出插入位置
                j--;
            }
            // 插入目标元素（j+1是最终插入位置）
            arr[j + 1] = target;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr)); // [2, 3, 4, 5, 8]
    }
}
2.3.2 希尔排序（插入排序升级版，高效）
一、核心原理

分组插入排序，是插入排序的优化版：

  1. 先将数组按「步长 gap」分组，每组单独进行插入排序；
  2. 逐步缩小步长（比如 gap/2），重复分组、插入排序；
  3. 当步长缩小到1时，整个数组变成一组，进行最后一次插入排序，完成排序。

核心：先粗排（大步长）、后细排（小步长），减少插入排序的移动次数。

二、流程示意图
1
2
3
4

原数组：[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
第1步：步长gap=5，分组：[10,5]、[9,4]、[8,3]、[7,2]、[6,1]，每组插入排序 → [5,4,3,2,1,10,9,8,7,6]
第2步：步长gap=2，分组：[5,3,1,9,7]、[4,2,10,8,6]，每组插入排序 → [1,2,3,4,5,6,7,8,9,10]
第3步：步长gap=1，整体插入排序（已接近有序，效率极高），排序完成
三、核心特点
  • 原地排序，不需要额外大量空间
  • 不稳定排序：相等元素相对顺序可能改变
  • 效率比插入排序高，适合中大规模数据
四、复杂度
项目 平均 最坏 最好
时间复杂度 (O(n^1.3)) (O(n^2)) (O(n))
空间复杂度 (O(1)) (O(1)) (O(1))
五、Java 实现
希尔排序 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

import java.util.Arrays;

public class ShellSort {

    /**
     * 希尔排序入口
     * @param arr 待排序数组
     */
    public static void shellSort(int[] arr) {
        int n = arr.length;
        // 步长gap初始化：n/2，每次缩小为原来的1/2，直到gap=1
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 按gap分组，每组进行插入排序
            // i从gap开始，逐个遍历每组的元素
            for (int i = gap; i < n; i++) {
                // 要插入的目标元素
                int target = arr[i];
                // j：当前组内，有序区间的最后一个元素下标
                int j = i - gap;

                // 组内插入排序：找到目标元素的插入位置
                while (j >= 0 && arr[j] > target) {
                    arr[j + gap] = arr[j]; // 元素后移（按gap步长）
                    j -= gap;
                }
                // 插入目标元素
                arr[j + gap] = target;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        shellSort(arr);
        System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    }
}

2.4 合并分治类排序

2.4.1 归并排序（稳定高效，适合需保留顺序场景）
一、核心原理

同样采用 分治思想，核心：先拆分、后合并

  1. 不断把数组从中间对半拆分，拆成最小单个元素；
  2. 单个元素天然有序，再两两合并成有序小数组；
  3. 持续向上合并，最终合并为一整个有序数组。
二、流程示意图
1
2
3
4
5

原数组：[12,11,13,5,6,7]
第一次拆分：[12,11,13]、[5,6,7]
继续拆分：[12,11] [13]、[5,6] [7]
拆到最小单元后，逐层有序合并
最终合并：[5, 6, 7, 11, 12, 13]
三、核心特点
  • 稳定排序：相等元素相对顺序保持不变
  • 需要额外临时数组空间，非原地排序
  • 时间复杂度稳定，不受原数组顺序影响
四、复杂度
项目 平均 最坏
时间复杂度 (O(n\log n)) (O(n\log n))
空间复杂度 (O(n)) (O(n))
五、Java 实现
归并排序 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

import java.util.Arrays;

public class MergeSort {

    /**
     * 归并排序入口：递归拆分
     * @param arr 待排序数组
     * @param left 左边界
     * @param right 右边界
     */
    public static void mergeSort(int[] arr, int left, int right) {
        // 区间有效，继续拆分
        if (left < right) {
            // 安全计算中间下标，防止溢出
            int mid = left + (right - left) / 2;
            // 递归拆分左半区
            mergeSort(arr, left, mid);
            // 递归拆分右半区
            mergeSort(arr, mid + 1, right);
            // 拆分完成，合并两个有序区间
            merge(arr, left, mid, right);
        }
    }

    /**
     * 合并两个有序子数组
     * [left,mid]  和  [mid+1,right]
     */
    private static void merge(int[] arr, int left, int mid, int right) {
        // 临时数组，存放合并后的有序元素
        int[] temp = new int[right - left + 1];
        // i：左区间起点  j：右区间起点  k：临时数组下标
        int i = left, j = mid + 1, k = 0;

        // 双指针对比，依次放入较小元素
        while (i <= mid && j <= right) {
            // 相等取左边，保证排序稳定性
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        // 左区间剩余元素直接追加
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        // 右区间剩余元素直接追加
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        // 把临时有序数组，拷贝回原数组对应区间
        System.arraycopy(temp, 0, arr, left, temp.length);
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr)); // [5, 6, 7, 11, 12, 13]
    }
}

2.5 非比较类排序（了解即可）

2.5.1 计数排序（适合数据范围小的场景）
一、核心原理

不比较元素大小，利用数组下标计数：

  1. 找到数组的最大值和最小值，确定计数范围；
  2. 创建计数数组，统计每个元素出现的次数；
  3. 遍历计数数组，按顺序将元素填充回原数组，完成排序。

核心：靠计数统计，而非元素对比，速度极快。

二、核心特点
  • 非比较排序，速度远快于比较类排序
  • 稳定排序
  • 需额外计数数组，数据范围越大，空间开销越大
  • 适合：数据范围小、整数类型的数组
三、复杂度
项目 平均 最坏 最好
时间复杂度 (O(n + k)) (O(n + k)) (O(n + k))
空间复杂度 (O(k)) (O(k)) (O(k))

（k：数组中元素的取值范围）

四、Java 实现
计数排序 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

import java.util.Arrays;

public class CountingSort {

    /**
     * 计数排序入口
     * @param arr 待排序数组（假设为非负整数）
     */
    public static void countingSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return; // 数组为空或只有1个元素，无需排序
        }

        // 1. 找到数组的最大值和最小值，确定计数范围
        int max = arr[0];
        int min = arr[0];
        for (int num : arr) {
            if (num > max) max = num;
            if (num < min) min = num;
        }

        // 2. 创建计数数组，长度 = 最大值 - 最小值 + 1（覆盖所有可能值）
        int[] countArr = new int[max - min + 1];

        // 3. 统计每个元素出现的次数
        for (int num : arr) {
            // 偏移量：将min映射到计数数组下标0
            countArr[num - min]++;
        }

        // 4. 遍历计数数组，填充回原数组
        int index = 0; // 原数组的下标
        for (int i = 0; i < countArr.length; i++) {
            // 计数不为0，说明该元素存在，重复填充
            while (countArr[i] > 0) {
                arr[index++] = i + min; // 还原元素值（加偏移量）
                countArr[i]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 2, 3, 0, 2, 3, 1};
        countingSort(arr);
        System.out.println(Arrays.toString(arr)); // [0, 1, 1, 2, 2, 3, 3, 3]
    }
}
2.5.2 基数排序、桶排序（简单了解）
一、基数排序
  • 原理：按数字的“位数”（个位、十位、百位…）分组排序，从低位到高位逐步排序；
  • 特点：稳定排序、非比较排序，适合整数、字符串排序，需额外空间；
  • 复杂度：时间 (O(d \times (n + k)))（d：最大数字的位数，k：基数，通常为10），空间 (O(n + k))。
二、桶排序
  • 原理：将数组元素分到多个“桶”中，每个桶单独排序（通常用插入排序），再合并所有桶；
  • 特点：稳定排序、非比较排序，适合数据分布均匀的场景，需额外空间；
  • 复杂度：时间 (O(n + k))（k：桶的数量），空间 (O(n + k))。

三、8大排序算法终极对比

排序算法 平均时间复杂度 空间复杂度 稳定性 核心特点
冒泡排序 O(n²) O(1) 稳定 逻辑最简单，相邻交换频繁
选择排序 O(n²) O(1) 不稳定 交换次数少，每次选最值放到对应位置
插入排序 O(n²) O(1) 稳定 数据接近有序时效率极高
希尔排序 O(n^1.3) O(1) 不稳定 插入排序升级版，分组增量排序
快速排序 O(n * log n) O(log n) 不稳定 综合效率最优，面试高频考点
归并排序 O(n * log n) O(n) 稳定 时间复杂度稳定，需要额外辅助空间
堆排序 O(n * log n) O(1) 不稳定 大根堆/小根堆实现，原地高效排序
计数排序 O(n+k) O(k) 稳定 非比较型排序，适合数值范围小的整数

四、背诵口诀

  1. 简单排序三兄弟：冒泡、选择、插入（(O(n^2))，原地）；
  2. 进阶排序三高手：快速、归并、堆（(O(n\log n))，高效）；
  3. 插入升级是希尔，不稳定、效率高；
  4. 非比较排序看计数，范围小、速度快；
  5. 稳定排序：冒泡、插入、归并、计数；
  6. 原地排序：除了归并、计数，其余都是。

3. 搜索算法

3.1 BFS（广度优先搜索）

一、核心原理
借助队列，遵循先入先出；
对树/图逐层遍历：先访问当前整层所有节点，再扩散到下一层，一圈一圈向外遍历。

二、流程示意图
以树形结构为例：

1
2
3
4
5

        ①
      /   \
     ②     ③
    / \   / \
   ④  ⑤ ⑥  ⑦

BFS 遍历顺序（按层）：
① → ② → ③ → ④ → ⑤ → ⑥ → ⑦

遍历逻辑：

  1. 先把根节点入队
  2. 出队一个节点，访问它
  3. 把该节点所有相邻子节点按顺序入队
  4. 循环出队、入队，直到队列为空

三、复杂度

项目 复杂度 说明
时间复杂度 (O(V+E)) V 顶点数，E 边数
空间复杂度 (O(V)) 队列+访问标记数组开销

四、核心特点

  1. 逐层扩散、辐射式遍历
  2. 无权图中第一次到达终点，就是最短路径
  3. 不会陷入一条分支死胡同

五、应用场景

  • 二叉树层序遍历
  • 迷宫/无权图最短路径
  • 图连通性检测
  • 多源最短路径、朋友圈分层

六、Java 实现（图BFS模板）

BFS 广度优先搜索 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

import java.util.LinkedList;
import java.util.Queue;

public class BFS {
    // 邻接矩阵表示图
    public static void bfs(int[][] graph, int start, boolean[] visited) {
        Queue<Integer> queue = new LinkedList<>();
        // 起始节点入队、标记已访问
        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            // 出队当前节点
            int cur = queue.poll();
            System.out.print(cur + " ");

            // 遍历所有相邻节点
            for (int i = 0; i < graph.length; i++) {
                // 有边相连 且 未被访问
                if (graph[cur][i] == 1 && !visited[i]) {
                    visited[i] = true;
                    queue.offer(i);
                }
            }
        }
    }

    public static void main(String[] args) {
        // 5个顶点 邻接矩阵
        int[][] graph = {
                {0, 1, 1, 0, 0},
                {1, 0, 0, 1, 1},
                {1, 0, 0, 0, 0},
                {0, 1, 0, 0, 0},
                {0, 1, 0, 0, 0}
        };
        boolean[] visited = new boolean[5];
        System.out.println("BFS遍历结果：");
        bfs(graph, 0, visited);
    }
}

3.2 DFS（深度优先搜索）

一、核心原理 借助递归/栈；
优先一条路走到底，走到没有未访问分支时，回溯退回到上一层，再走其他分支。

二、流程示意图 同树形结构：

1
2
3
4
5

        ①
      /   \
     ②     ③
    / \   / \
   ④  ⑤ ⑥  ⑦

DFS 遍历顺序（一路深搜+回溯）：
① → ② → ④ → ⑤ → ③ → ⑥ → ⑦

遍历逻辑：

  1. 访问当前节点，标记已访问
  2. 只要有未访问邻接点，就递归深入走下去
  3. 无路可走时自动回溯，回头走其他分支

三、复杂度

项目 复杂度 说明
时间复杂度 (O(V+E)) V 顶点数，E 边数
空间复杂度 (O(V)) 递归栈深度+访问数组

四、核心特点

  1. 一条路走到黑，走不通再回溯
  2. 能枚举所有路径、所有方案
  3. 不保证首次路径最短

五、应用场景

  • 全路径枚举、子集/组合问题
  • 岛屿数量、封闭区域搜索
  • 图连通分量遍历
  • 拓扑排序、回溯类算法基础

六、Java 实现（递归版DFS模板）

DFS 深度优先搜索 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class DFS {
    // 递归实现深度优先搜索
    public static void dfs(int[][] graph, int cur, boolean[] visited) {
        // 标记当前节点已访问
        visited[cur] = true;
        System.out.print(cur + " ");

        // 遍历所有相邻节点
        for (int i = 0; i < graph.length; i++) {
            // 有边相连 且 未访问，递归深入
            if (graph[cur][i] == 1 && !visited[i]) {
                dfs(graph, i, visited);
            }
        }
    }

    public static void main(String[] args) {
        // 5个顶点邻接矩阵
        int[][] graph = {
                {0, 1, 1, 0, 0},
                {1, 0, 0, 1, 1},
                {1, 0, 0, 0, 0},
                {0, 1, 0, 0, 0},
                {0, 1, 0, 0, 0}
        };
        boolean[] visited = new boolean[5];
        System.out.println("\nDFS遍历结果：");
        dfs(graph, 0, visited);
    }
}

4. 动态规划

一、核心思想

把大问题拆解成若干重复的子问题，保存子问题计算结果，避免重复递归、重复计算；
用空间换时间，逐步递推得到整体最优解。

二、适用必备条件

  1. 重叠子问题：不同大问题会共用相同子问题，存在大量重复计算
  2. 最优子结构：子问题的最优解，可以推导出原问题的最优解

4.1 斐波那契数列

一、问题描述

求斐波那契第 n 项：
F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)

二、暴力递归缺陷

  • 时间复杂度：O(2n)
  • 存在海量重复子问题计算，n 稍大就严重超时

三、DP 优化思路

用数组/变量记录已经算过的子问题结果，从底向上递推，只算一遍。

四、复杂度

方案 时间复杂度 空间复杂度
暴力递归 O(2n) O(n) 递归栈
DP 数组版 O(n) O(n)
空间优化版 O(n) O(1)

五、流程逻辑

  1. 初始 base 条件：dp[0]=0, dp[1]=1
  2. 从 i=2 开始循环递推：dp[i] = dp[i-1] + dp[i-2]
  3. 直接取出记录结果，无重复计算

六、Java 实现

斐波那契数列 DP 完整版代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public class FibonacciDP {

    // DP数组版本
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    // 空间优化：只保留前两个数，滚动变量
    public static int fibonacciOpt(int n) {
        if (n <= 1) {
            return n;
        }
        int a = 0;
        int b = 1;
        for (int i = 2; i <= n; i++) {
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(10));
        System.out.println(fibonacciOpt(10));
    }
}

4.2 0-1 背包问题

一、问题描述

给定 n 个物品，每个物品有重量 w[i]、价值 v[i]；
背包最大容量为 W，每个物品只能选或不选，求背包能装的最大价值。

二、DP 状态定义

  • dp[i][j]：前 i 个物品，背包容量 j，能装的最大价值
  • w[i]：第 i 个物品重量
  • v[i]：第 i 个物品价值

动态规划必须从 0 开始初始化！

  • dp[0][j]：0 个物品，价值一定是 0
  • dp[i][0]：0 容量，价值一定是 0

三、状态转移方程

1
2
3
4
5
6

// 不选第i个物品：继承前i-1件、容量j的价值
// 选第i个物品：前i-1件、容量腾出w[i] + 当前物品价值
dp[i][j] = max(
    dp[i-1][j],
    dp[i-1][j - w[i]] + v[i]
)

四、复杂度

项目 复杂度
时间复杂度 O(n×W)
空间复杂度 O(n×W)

五、流程逻辑

  1. 初始化二维 dp 数组，0 个物品、任意容量价值都为 0
  2. 遍历每个物品 i，再遍历每个背包容量 j
  3. 容量放不下当前物品：只能不选，继承上一行结果
  4. 容量放得下：在「选 / 不选」中取最大值
  5. 最终 dp[n][W] 即为最大价值

六、Java 实现

0-1背包 二维DP完整代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

public class Knapsack01 {

    /**
     * @param W 背包容量
     * @param w 物品重量数组
     * @param v 物品价值数组
     * @param n 物品个数
     * @return 最大价值
     */
    public static int knapsack(int W, int[] w, int[] v, int n) {
        // dp[i][j]：前i个物品，容量j的最大价值
        // n+1：表示 0 ~ n 个物品
        // W+1：表示 0 ~ W 容量
        int[][] dp = new int[n + 1][W + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= W; j++) {
                // 判断当前背包容量是否装下第i件物品
                if (j >= w[i - 1]) {
                    // 装得下：可以选 装 或 不装
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
                } else {
                    // 装不下：只能不装
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][W];
    }

    public static void main(String[] args) {
        int W = 5;
        int[] w = {2, 3, 4};
        int[] v = {3, 4, 5};
        int n = 3;
        System.out.println(knapsack(W, w, v, n));
    }
}

5. 贪心算法

一、核心思想

在每一步做出当前看起来最优的选择（局部最优），从而希望最终得到全局最优解。
核心：只顾眼前最优，不回头，不回溯。

二、关键特点

  1. 局部最优 → 期望全局最优
  2. 不保存历史结果，不回溯
  3. 效率极高，通常为 O(n log n)
  4. 不是所有问题都适用，必须满足贪心选择性质

三、适用条件

  1. 贪心选择性质：局部最优能推导出全局最优
  2. 最优子结构：问题的最优解包含子问题的最优解

5.1 活动选择问题

一、问题描述

给定多个活动，每个活动有开始时间和结束时间。
目标：选出最多的、互相不重叠的活动。

二、贪心策略

按结束时间升序排序，每次选择结束最早、且不与已选活动冲突的活动。
（结束越早，留给后面活动的时间越多，能选的活动总数就越多）

三、复杂度

项目 复杂度
时间复杂度 O(n log n)
空间复杂度 O(n)

四、执行流程

  1. 将所有活动按结束时间从小到大排序
  2. 初始化上一个活动结束时间
  3. 遍历活动：如果当前活动开始时间 ≥ 上一个结束时间，就选中
  4. 更新结束时间，继续遍历

例如：

1
2
3
4

(1,3) 开始1 结束3
(2,4) 开始2 结束4
(3,5) 开始3 结束5
(5,7) 开始5 结束7

最终选中的活动

1
2
3

(1,3)
(3,5)
(5,7)

五、Java 完整实现

活动选择（贪心标准代码） 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class ActivitySelection {
    /**
     * 贪心活动选择：选最多不重叠活动
     * @param activities 活动数组 int[]{开始时间, 结束时间}
     * @return 选中的活动列表
     */
    public static List<int[]> selectActivities(List<int[]> activities) {
        // 1. 按结束时间升序排序（贪心核心）
        activities.sort(Comparator.comparingInt(a -> a[1]));

        List<int[]> selected = new ArrayList<>();
        int lastEnd = -1; // 上一个选中活动的结束时间

        // 2. 遍历选择
        for (int[] activity : activities) {
            int start = activity[0];
            int end = activity[1];
            // 当前活动开始时间 >= 上一个结束时间 → 不冲突，可以选
            if (start >= lastEnd) {
                selected.add(activity);
                lastEnd = end;
            }
        }
        return selected;
    }

    // 测试
    public static void main(String[] args) {
        List<int[]> activities = new ArrayList<>();
        activities.add(new int[]{1, 3});
        activities.add(new int[]{2, 4});
        activities.add(new int[]{3, 5});
        activities.add(new int[]{5, 7});

        List<int[]> res = selectActivities(activities);
        System.out.println("选中活动数量：" + res.size());
        for (int[] a : res) {
            System.out.println(Arrays.toString(a));
        }
    }
}

6. 回溯算法

一、核心思想

本质是暴力枚举所有可能的“试探+回退”算法；
一条路走下去，不满足条件就回头（回溯），尝试其他分支，直到找到所有解。
可以理解为：走不通就回头，换条路再走。

二、核心特点

  1. 是一种穷举搜索，能找到所有合法方案
  2. 依靠递归实现，递归前进，回溯回退
  3. 必须恢复现场（撤销选择），这是回溯的标志
  4. 效率一般，但能解决大多数排列、组合、枚举类问题

三、适用场景

  • 全排列、子集、组合问题
  • 棋盘问题（八皇后、数独）
  • 路径搜索、分割问题
  • 需要枚举所有可能解的场景

6.1 全排列

一、问题描述

给定一个无重复数字的数组，返回它的所有可能的全排列。
例如：[1,2,3] → 输出 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

二、回溯思路（交换法）

  1. 固定第 1 位，交换枚举每一个数字
  2. 递归固定第 2 位、第 3 位……
  3. 当固定到最后一位，得到一个完整排列
  4. 交换回去（回溯），恢复数组，继续枚举其他方案

三、复杂度

项目 复杂度
时间复杂度 O(n × n!)
空间复杂度 O(n)

四、执行流程

  1. 从第 start 位开始，依次和后面每一位交换
  2. 递归处理下一位 start+1
  3. 当 start == 数组长度，说明形成一个完整排列，加入结果集
  4. 回溯：把交换的数字换回来，恢复数组状态，继续尝试下一种排列

五、Java 实现

全排列（回溯交换法） 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

import java.util.ArrayList;
import java.util.List;

public class Permutation {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, result);
        return result;
    }

    /**
     * 回溯递归
     * @param nums 数组
     * @param start 当前要固定的位置
     * @param result 结果集合
     */
    private void backtrack(int[] nums, int start, List<List<Integer>> result) {
        // 递归终止：已经到最后一位，形成一个排列
        if (start == nums.length) {
            List<Integer> list = new ArrayList<>();
            for (int num : nums) {
                list.add(num);
            }
            result.add(list);
            return;
        }

        // 枚举：把 i 位置的数交换到 start 位置
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);         // 做选择
            backtrack(nums, start + 1, result); // 递归下一位
            swap(nums, start, i);         // 撤销选择（回溯核心）
        }
    }

    // 交换数组两个位置
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // 测试
    public static void main(String[] args) {
        Permutation p = new Permutation();
        int[] nums = {1, 2, 3};
        System.out.println(p.permute(nums));
    }
}

三、复杂度对比总结

1. 数据结构复杂度

数据结构 访问 搜索 插入 删除
数组 O(1) O(n) O(n) O(n)
链表 O(n) O(n) O(1)* O(1)*
栈 O(n) - O(1) O(1)
队列 O(n) - O(1) O(1)
哈希表 - O(1) O(1) O(1)
BST（平衡） O(log n) O(log n) O(log n) O(log n)
堆 - - O(log n) O(log n)
Trie O(L) O(L) O(L) O(L)
图（邻接表） O(V) O(V+E) O(1) O(E)

2. 排序算法对比

算法 平均 最坏 空间 稳定性
快速排序 O(n log n) O(n²) O(log n) 不稳定
归并排序 O(n log n) O(n log n) O(n) 稳定
堆排序 O(n log n) O(n log n) O(1) 不稳定
冒泡排序 O(n²) O(n²) O(1) 稳定

四、常见应用场景

数据结构/算法 典型应用
数组 随机访问、缓存
链表 LRU缓存、邻接表
栈 函数调用栈、括号匹配
队列 任务调度、消息队列
哈希表 缓存、查找表
BST 数据库索引、有序数据
堆 优先级队列、TopK
Trie 前缀匹配、自动补全
图 社交网络、路径规划
DP 背包问题、最长公共子序列
贪心 活动选择、哈夫曼编码
回溯 八皇后、排列组合