数据结构与算法

写代码越久越发现——业务千变万化，但底层都是数据结构 + 算法。一个 list 怎么存最快查找？一段代码为什么慢？怎么在百万数据里找前 K 个？这些都要靠数据结构和算法知识。这一章我们把核心——复杂度、链表栈队列、树、哈希、排序、常见算法套路——一次过一遍。

一、复杂度分析

时间复杂度（Time Complexity）——算法运行时间随输入规模 n 增长的趋势，用大 O 表示法（Big-O Notation）。

复杂度	名字	例子	n=100 万时
`O(1)`	常数	数组取下标	1 步
`O(log n)`	对数	二分查找	20 步
`O(n)`	线性	遍历数组	100 万步
`O(n log n)`	线性对数	快排/归并	2000 万步
`O(n²)`	平方	冒泡/选择	1 万亿步
`O(2ⁿ)`	指数	暴力子集	宇宙爆炸

空间复杂度（Space Complexity）——额外内存随 n 的增长趋势。

经验：

O(n²) 在 n > 1 万时已经慢得不行——必须优化。
O(n log n) 是排序算法的”下界”——比较排序最快就这样。
O(log n) 几乎等于”常数”——二分、平衡树的高度都是 log n。

二、线性结构

2.1 数组

数组——内存连续、固定大小、O(1) 随机访问、O(n) 插入删除。Java 的 ArrayList 底层是数组——容量不够时自动扩容（1.5 倍）。

2.2 链表

链表——内存不连续、节点串起来、O(1) 头插删、O(n) 随机访问。

class Node {
    int val;
    Node next;
    Node(int v) { val = v; }
}

// 单链表反转 (经典面试题)
Node reverse(Node head) {
    Node prev = null, cur = head;
    while (cur != null) {
        Node next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

LinkedList 是双向链表——add/remove 头尾 O(1)，随机 get(i) 是 O(n)。所以LinkedList 几乎不用——ArrayList 即使插入也大多比它快（CPU 缓存友好）。

2.3 栈

栈——后进先出（LIFO）。push/pop/peek 都 O(1)。

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2);
stack.peek();   // 2
stack.pop();    // 2

应用：括号匹配、表达式求值、函数调用栈、DFS。ArrayDeque 比 Stack（老类）快——Stack 继承 Vector 全方法同步，开销大。

2.4 队列

队列——先进先出（FIFO）。offer/poll/peek 都 O(1)。

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2);
queue.peek();   // 1
queue.poll();   // 1

应用：BFS、生产者消费者、任务调度。ArrayDeque 普通队列，PriorityQueue 优先队列（堆），LinkedBlockingQueue 阻塞队列（线程池用）。

三、树

3.1 二叉树

每个节点最多两个子节点。

class TreeNode {
    int val;
    TreeNode left, right;
}

// 三种遍历
void preOrder(TreeNode n) {   // 前序: 根-左-右
    if (n == null) return;
    System.out.println(n.val);
    preOrder(n.left);
    preOrder(n.right);
}
void inOrder(TreeNode n) {    // 中序: 左-根-右 (BST 得到有序)
    if (n == null) return;
    inOrder(n.left);
    System.out.println(n.val);
    inOrder(n.right);
}

3.2 二叉搜索树（BST）

左子树都＜根，右子树都＞根。中序遍历得到有序序列。查找/插入/删除平均 O(log n)，最坏 O(n)（退化成链表）。

3.3 平衡树：红黑树 / AVL

BST 退化成链表就慢——平衡树通过旋转保持平衡。AVL 严格平衡（左右高度差 ≤ 1），红黑树弱平衡（最长路径不超最短 2 倍）。

AVL —— 查询多增删少（严格平衡，查询快）。
红黑树 —— 增删多（弱平衡，旋转少）。Java 的 TreeMap/HashMap（链表超 8 转红黑树）都是红黑树。

3.4 B 树 / B+ 树

多路平衡查找树——每个节点多个子节点、多个关键字。B+ 树的所有数据在叶子，叶子串成链表。

为什么数据库用 B+ 树不用红黑树？因为磁盘 IO 是块读的——B+ 树矮胖，一次读一个节点（一页）能拿很多关键字，IO 次数少（树高度低）。MySQL 索引就是 B+ 树。

3.5 堆

堆——完全二叉树，父节点 ≥/≤ 子节点（最大/最小堆）。PriorityQueue 是最小堆。

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

maxHeap.offer(3); maxHeap.offer(1); maxHeap.offer(2);
maxHeap.peek();   // 3 (最大)
maxHeap.poll();   // 3

应用：Top K 问题、合并 K 个有序链表、任务调度。堆的插入/删除是 O(log n)。

四、哈希表

哈希表——key 经过哈希函数算出数组下标，O(1) 平均查找。

Map<String, Integer> map = new HashMap<>();
map.put("张三", 20);   // hash("张三") % 桶数 -> 桶下标
map.get("张三");       // 同样算下标, O(1) 取

4.1 哈希冲突

不同 key 哈希到同一下标——冲突。两种解法：

链地址法（Separate Chaining） —— 每个桶挂链表。Java HashMap 用这个。链表超 8 转红黑树（防哈希攻击）。
开放地址法（Open Addressing） —— 冲突就找下一个空位（线性探测、二次探测、双哈希）。ThreadLocalMap 用这个。

4.2 负载因子与扩容

HashMap 默认初始 16 桶，负载因子 0.75——元素数 > 16×0.75=12 就扩容到 32，重新哈希。扩容代价大（O(n)），所以预估大小可以预分配。

4.3 一致性哈希

分布式缓存用——节点增减时只影响相邻段数据，不全部重新哈希。Redis Cluster 的哈希槽是类似思想。

五、排序算法

算法	平均	最坏	空间	稳定
冒泡	O(n²)	O(n²)	O(1)	✅
选择	O(n²)	O(n²)	O(1)	❌
插入	O(n²)	O(n²)	O(1)	✅
快排	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)	❌

稳定——相等元素相对顺序不变。Arrays.sort 对基本类型用快排（不稳定），对象用 TimSort（归并改进，稳定）。

5.1 快排

void quickSort(int[] arr, int low, int high) {
    if (low >= high) return;
    int pivot = partition(arr, low, high);
    quickSort(arr, low, pivot - 1);
    quickSort(arr, pivot + 1, high);
}

int partition(int[] arr, int low, int high) {
    int pivot = arr[high];   // 选最右为基准
    int i = low - 1;          // i 是"小于 pivot 区"的边界
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return i + 1;
}

void swap(int[] arr, int a, int b) {
    int t = arr[a]; arr[a] = arr[b]; arr[b] = t;
}

快排思想——选基准，比它小的放左、大的放右，递归排两边。最坏 O(n²)（已排序数组 + 选端点为基准），随机化基准或三数取中可避免。

5.2 归并

void mergeSort(int[] arr, int[] temp, int low, int high) {
    if (low >= high) return;
    int mid = (low + high) / 2;
    mergeSort(arr, temp, low, mid);
    mergeSort(arr, temp, mid + 1, high);
    merge(arr, temp, low, mid, high);
}

void merge(int[] arr, int[] temp, int low, int mid, int high) {
    int i = low, j = mid + 1, k = low;
    while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= high) temp[k++] = arr[j++];
    System.arraycopy(temp, low, arr, low, high - low + 1);
}

归并——分治拆到单个元素，再两两合并。稳定排序，O(n log n) 稳定，但要 O(n) 额外空间。

5.3 堆排

建最大堆 → 顶交换到末尾 → 缩堆 → 重新堆化。原地排序，空间 O(1)。

六、常见算法套路

6.1 双指针

快慢指针 —— 链表找中点、检测环。
左右指针 —— 二分、两数之和（排序数组）。

// 判断链表有环
boolean hasCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

6.2 滑动窗口

维护一个窗口，左右指针滑动——求最长/最短子串。

// 无重复字符的最长子串长度
int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> last = new HashMap<>();
    int left = 0, max = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (last.containsKey(c) && last.get(c) >= left) {
            left = last.get(c) + 1;
        }
        last.put(c, right);
        max = Math.max(max, right - left + 1);
    }
    return max;
}

6.3 二分查找

int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;   // 防 int 溢出
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

二分前提——数组有序。mid = low + (high - low) / 2 而不是 (low + high) / 2——后者 low + high 可能 int 溢出（Joshua Bloch 在 JDK 9 修的著名 bug）。

6.4 动态规划入门

动态规划（DP）——把大问题拆成子问题，记忆子问题答案避免重复计算。

经典：斐波那契。

// 递归 (O(2^n), 重复计算)
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

// DP (O(n), 记忆化)
int fibDp(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];
}

经典：爬楼梯——n 阶楼梯，每次走 1 或 2 步，多少种走法？

// 状态转移: dp[i] = dp[i-1] + dp[i-2]
int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        int c = a + b;
        a = b; b = c;
    }
    return b;
}

DP 三步——定义状态、写出转移方程、确定初始值和计算顺序。

6.5 BFS / DFS

// 二叉树层序遍历 (BFS)
List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode n = q.poll();
            level.add(n.val);
            if (n.left != null) q.offer(n.left);
            if (n.right != null) q.offer(n.right);
        }
        res.add(level);
    }
    return res;
}

BFS——队列、层序、最短路径（无权图）。DFS——栈/递归、深度优先、连通性、拓扑排序。

七、实战：快排与算法演示

import java.util.*;
import java.util.stream.*;

public class Main {
  public static void main(String[] args) {
      System.out.println("=== 数据结构与算法演示 ===\n");

// 1. 快速排序
      System.out.println("--- 1. 快速排序 ---");
      int[] arr = {5, 2, 8, 1, 9, 3, 7, 4, 6};
      System.out.println("排序前: " + Arrays.toString(arr));
      quickSort(arr, 0, arr.length - 1);
      System.out.println("排序后: " + Arrays.toString(arr));

// 2. 二分查找
      System.out.println("\n--- 2. 二分查找 ---");
      int[] sorted = {1, 3, 5, 7, 9, 11, 13, 15};
      System.out.println("数组: " + Arrays.toString(sorted));
      System.out.println("查找 7: 索引=" + binarySearch(sorted, 7));
      System.out.println("查找 8: 索引=" + binarySearch(sorted, 8) + " (-1 不存在)");

// 3. 哈希表 (HashMap 冲突链表演示)
      System.out.println("\n--- 3. 哈希表 ---");
      Map<String, Integer> map = new HashMap<>(16);
      map.put("张三", 20);
      map.put("李四", 22);
      map.put("王五", 25);
      System.out.println("map = " + map);
      System.out.println("取 张三: " + map.get("张三") + " (O(1) 平均)");
      System.out.println("HashMap 桶数=16, 负载因子=0.75, >12 扩容");

// 4. 堆: Top K
      System.out.println("\n--- 4. 堆求 Top 3 ---");
      int[] data = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
      System.out.println("数据: " + Arrays.toString(data));
      PriorityQueue<Integer> minHeap = new PriorityQueue<>();   // 最小堆
      for (int x : data) {
          minHeap.offer(x);
          if (minHeap.size() > 3) minHeap.poll();   // 超过 3 踢最小
      }
      System.out.println("Top 3 (最大的 3 个): " + minHeap);

// 5. 双指针: 判断链表有环
      System.out.println("\n--- 5. 双指针: 链表有环 ---");
      Node n1 = new Node(1);
      Node n2 = new Node(2);
      Node n3 = new Node(3);
      Node n4 = new Node(4);
      n1.next = n2; n2.next = n3; n3.next = n4;
      System.out.println("1->2->3->4 有环? " + hasCycle(n1));
      n4.next = n2;   // 制造环 4 -> 2
      System.out.println("1->2->3->4->2(环) 有环? " + hasCycle(n1));

// 6. 滑动窗口: 最长无重复子串
      System.out.println("\n--- 6. 滑动窗口: 最长无重复子串 ---");
      System.out.println("abcabcbb 最长: " + lengthOfLongestSubstring("abcabcbb"));
      System.out.println("bbbbb 最长: " + lengthOfLongestSubstring("bbbbb"));
      System.out.println("pwwkew 最长: " + lengthOfLongestSubstring("pwwkew"));

// 7. 动态规划: 斐波那契
      System.out.println("\n--- 7. 动态规划: 斐波那契 ---");
      for (int n = 0; n <= 10; n++) {
          System.out.println("fib(" + n + ") = " + fibDp(n));
      }
      System.out.println("fib(40) = " + fibDp(40) + " (递归会算到爆炸, DP 秒出)");

// 8. 动态规划: 爬楼梯
      System.out.println("\n--- 8. 动态规划: 爬楼梯 ---");
      for (int n = 1; n <= 8; n++) {
          System.out.println("爬 " + n + " 阶: " + climbStairs(n) + " 种");
      }

// 9. 复杂度对比
      System.out.println("\n--- 9. 复杂度直观对比 (排序 100 万随机数) ---");
      int[] big = new Random(42).ints(1_000_000, 0, 1_000_000).toArray();
      int[] copy1 = big.clone();
      int[] copy2 = big.clone();

long t1 = System.currentTimeMillis();
      Arrays.sort(copy1);   // JDK 双轴快排
      long t2 = System.currentTimeMillis();
      System.out.println("JDK Arrays.sort (双轴快排 O(n log n)): " + (t2 - t1) + " ms");

// 注: 冒泡 O(n^2) 在百万级要算很久, 这里跳过
      System.out.println("冒泡 O(n^2) 在 100 万数据下理论上要数小时, 不实测");

System.out.println("\n=== 数据结构与算法要点 ===");
      System.out.println("1. 大 O: O(1) < O(log n) < O(n) < O(n log n) < O(n^2)");
      System.out.println("2. 链表 O(1) 增删头尾, O(n) 随机访问");
      System.out.println("3. 二叉搜索树中序遍历有序");
      System.out.println("4. 红黑树: Java TreeMap/HashMap(链表>8 转红黑树)");
      System.out.println("5. B+树: 数据库索引, 矮胖适合磁盘 IO");
      System.out.println("6. 堆: PriorityQueue, Top K 问题");
      System.out.println("7. 哈希冲突: 链地址(HashMap) / 开放地址(ThreadLocalMap)");
      System.out.println("8. 快排平均 O(n log n), 最坏 O(n^2), 不稳定");
      System.out.println("9. 归并稳定 O(n log n), 需 O(n) 空间");
      System.out.println("10. DP: 状态定义 + 转移方程 + 初始值");
  }

// === 快排 ===
  static void quickSort(int[] arr, int low, int high) {
      if (low >= high) return;
      int pivot = partition(arr, low, high);
      quickSort(arr, low, pivot - 1);
      quickSort(arr, pivot + 1, high);
  }

static int partition(int[] arr, int low, int high) {
      int pivot = arr[high];
      int i = low - 1;
      for (int j = low; j < high; j++) {
          if (arr[j] < pivot) {
              i++;
              swap(arr, i, j);
          }
      }
      swap(arr, i + 1, high);
      return i + 1;
  }

static void swap(int[] arr, int a, int b) {
      int t = arr[a]; arr[a] = arr[b]; arr[b] = t;
  }

// === 二分查找 ===
  static int binarySearch(int[] arr, int target) {
      int low = 0, high = arr.length - 1;
      while (low <= high) {
          int mid = low + (high - low) / 2;
          if (arr[mid] == target) return mid;
          if (arr[mid] < target) low = mid + 1;
          else high = mid - 1;
      }
      return -1;
  }

// === 双指针: 链表有环 ===
  static boolean hasCycle(Node head) {
      Node slow = head, fast = head;
      while (fast != null && fast.next != null) {
          slow = slow.next;
          fast = fast.next.next;
          if (slow == fast) return true;
      }
      return false;
  }

// === 滑动窗口: 最长无重复子串 ===
  static int lengthOfLongestSubstring(String s) {
      Map<Character, Integer> last = new HashMap<>();
      int left = 0, max = 0;
      for (int right = 0; right < s.length(); right++) {
          char c = s.charAt(right);
          if (last.containsKey(c) && last.get(c) >= left) {
              left = last.get(c) + 1;
          }
          last.put(c, right);
          max = Math.max(max, right - left + 1);
      }
      return max;
  }

// === DP: 斐波那契 ===
  static int fibDp(int n) {
      if (n <= 1) return n;
      int a = 0, b = 1;
      for (int i = 2; i <= n; i++) {
          int c = a + b;
          a = b; b = c;
      }
      return b;
  }

// === DP: 爬楼梯 ===
  static int climbStairs(int n) {
      if (n <= 2) return n;
      int a = 1, b = 2;
      for (int i = 3; i <= n; i++) {
          int c = a + b;
          a = b; b = c;
      }
      return b;
  }

static class Node {
      int val;
      Node next;
      Node(int v) { val = v; }
  }
}

观察重点：

快排原地排序——分区 + 递归，O(n log n) 平均。

二分查找每次折半——O(log n)，100 万数据只 20 步。

最小堆求 Top K——堆大小固定 K，超了踢最小，剩下就是 Top K。

快慢指针检测环——快指针追上慢指针就有环。

滑动窗口维护不重复字符——左右指针夹出无重复区间。

DP 把递归 O(2ⁿ) 优化到 O(n)——记忆化避免重复计算。

八、本章小结

概念	核心要点
大 O	时间/空间复杂度趋势
链表	O(1) 增删头尾，O(n) 随机访问
栈/队列	LIFO/FIFO，O(1) 操作
二叉搜索树	中序有序，平均 O(log n)
红黑树	弱平衡，Java `TreeMap`/`HashMap` 用
B+ 树	数据库索引，矮胖适配磁盘 IO
堆	`PriorityQueue`，Top K 问题
哈希冲突	链地址 / 开放地址
快排	O(n log n) 平均，O(n²) 最坏，不稳定
归并	稳定 O(n log n)，O(n) 空间
动态规划	状态 + 转移方程 + 初始值

记忆口诀：

大 O 看趋势——O(1) 最好，O(n²) 要优化。
数组随机访问快，链表增删快——权衡选。
BST 中序有序——左根右遍历。
HashMap 链表 > 8 转红黑树——防哈希攻击。
快排平均 O(n log n)——分区 + 递归。
二分 O(log n)——前提是有序。
DP 三步——状态、转移、初始。

结语：算法是内功

这一章我们过了一遍数据结构和算法核心——它们是编程的”内功”，业务框架千变万化，内功永远用得上。下一章看分布式缓存的王者——Redis。