Java 从零到精通

简体中文

English

简体中文

English

Appearance

算法入门 ​

学习目标 ​

  • 理解算法描述的是“解决问题的步骤”和“步骤增长的成本”。
  • 掌握顺序查找和二分查找的基本行为与适用前提。
  • 读懂选择排序和插入排序的核心循环。
  • 用 Big O 直观描述 O(1)、O(n) 和 O(n^2)。
  • 通过 JUnit 5 测试验证空数组、边界索引、重复值和输入不被修改等行为。

前置知识 ​

已完成数据结构基础，知道数组、列表、栈、队列、Map 的基本行为，并能运行 starter / solution 双模块练习。

练习入口 ​

本章对应仓库中的算法入门练习：

运行 starter：

bash
mvn -B -pl exercises/algorithms-basics/starter -am test

运行参考答案：

bash
mvn -B -pl exercises/algorithms-basics/solution -am test

算法先问什么 ​

算法不是只为了面试刷题。日常开发中，你会不断遇到这些问题：

  1. 我要找的数据是否可能不存在？
  2. 输入是否已经有序？
  3. 当前写法在 10 条数据和 10000 条数据时差别有多大？
  4. 排序是否会修改原始数据？

本章用小数组练习这些问题，重点是行为、边界和复杂度直觉。

顺序查找 ​

顺序查找从头到尾检查每个元素。它的优点是简单，不要求数据有序；缺点是最坏情况下需要看完整个数组。

练习中的 LinearSearch 覆盖：

  • 找到目标值时返回索引。
  • 找不到目标值时返回 -1。
  • 有重复值时返回第一个索引。
  • 空数组直接返回 -1。

这种查找通常是 O(n)：数组越长，最多要看的元素越多。

二分查找 ​

二分查找每次检查中间位置，并把搜索范围缩小一半。它很快，但前提非常重要：输入必须已经按升序排列。

练习中的 BinarySearch 覆盖：

  • 找到中间位置的目标值。
  • 找到左边界和右边界目标值。
  • 找不到目标值时返回 -1。
  • 空数组返回 -1。

二分查找通常是 O(log n)。初学阶段先记住它的直觉：每次都扔掉一半候选范围。

选择排序 ​

选择排序的思路是每一轮从未排序区间里找最小值，把它放到当前位置。

基本步骤：

  1. 从第 0 个位置开始。
  2. 在后续元素里找到最小值的位置。
  3. 把当前位置和最小值位置交换。
  4. 继续处理下一个位置。

选择排序容易理解，但通常是 O(n^2)。本章用它练习双重循环、交换和重复值。

插入排序 ​

插入排序把左侧看成已经有序的区域。每次拿一个新元素，把它插入到左侧合适的位置。

基本步骤：

  1. 从第 1 个元素开始。
  2. 保存当前值。
  3. 把左侧更大的元素向右移动。
  4. 把当前值放入空出来的位置。

插入排序最坏情况也是 O(n^2)，但在小规模或接近有序的数据上很直观，代码也常用于解释“局部有序”的思想。

Big O 直觉 ​

Big O 关注输入规模增长时，步骤数量如何变化。

表达规模为 5规模为 100直觉
O(1)11固定次数
O(n)5100跟输入规模一起增长
O(n^2)2510000两层遍历会快速变大

练习中的 ComplexityExplorer 不做真实业务，而是用计数返回步骤数量，帮助你把抽象复杂度和具体数字连起来。

分级练习 ​

  • 基础：完成 LinearSearch，覆盖找到、找不到、重复值和空数组。
  • 进阶：完成 BinarySearch，画出每轮 left、middle、right 的变化。
  • 挑战：完成两个排序类，并说明为什么测试要求“不修改传入数组”。

常见错误与排查 ​

  • 二分查找忘记移动 left 或 right：循环可能永远不结束。
  • 二分查找把无序数组当输入：结果不可靠，先确认前提。
  • 选择排序找到最小值后忘记交换：数组不会真正变有序。
  • 插入排序移动元素后忘记写回当前值：数据会丢失或重复。
  • 排序直接修改传入数组：调用者可能失去原始顺序。

面试与复习题 ​

  1. 顺序查找为什么不要求数组有序？
  2. 二分查找为什么要求输入已经有序？
  3. left + (right - left) / 2 比 (left + right) / 2 更稳妥在哪里？
  4. 选择排序每一轮确定了哪个位置的最终值？
  5. 插入排序为什么需要把元素向右移动？
  6. O(n) 和 O(n^2) 在输入规模变大时差别在哪里？
  7. 排序函数是否应该修改传入数组？这取决于什么约定？

本章总结 ​

算法入门的重点不是背模板，而是能说清楚输入、输出、前提、边界和成本。完成本章后，你已经能用 Java 写出最基础的查找和排序，并能用测试保护它们的行为。

下一步 ​

上一章：数据结构基础

下一章：网络基础