第 5 章 · 数组

数组是第一种「批量装数据」的容器,也是 Java 和 C 的差异最直观的地方:同一个概念,C 里是裸内存(指针课第 4 章:退化、丢长度、越界是 UB),Java 里是自带长度的对象(越界抛异常,报错直接带下标)。本章过一遍 Java 数组的全部家当:创建、遍历、二维数组(它其实是指针数组的表亲)、以及 Arrays 工具类的日常三件套。学过数据结构课的话,这一章会和它的线性表、排序两章频繁握手。

5.1 创建与遍历:对象语义先立住

int[] a = new int[5];          // 动态创建,5 个元素自动初始化为 0
int[] b = {1, 2, 3, 4, 5};     // 静态初始化,长度由花括号定
int n = b.length;              // 长度是 final 属性,创建后不可变

先建立一个正确的心理模型:数组是对象,变量 b 里存的是引用(门牌号)。这解释了两件事:int[] c = b; 拷的是门牌不是数据(两个变量指向同一个数组,改一个另一个看得见,第 10 章集合类深化);把 null 数组传入方法再访问,抛 NullPointerException。基础类型数组 new int[5] 自动清零(计组课第 6 章讲过的「calloc 语义」),对象数组 new String[5] 初始化为 null(引用的默认值)。

遍历两种(第 4 章讲过选择标准):需要下标用传统 for,否则增强 for。越界的报错值得认识一下,它比 C 的 UB 友好太多:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException:
Index 5 out of bounds for length 5
        at Main.main(Main.java:7)      ← 连第几行都告诉你

5.2 手写一遍冒泡,然后忘掉它

冒泡排序是理解循环嵌套的经典练习(数据结构课第 8 章完整分析过它的复杂度与稳定性):

for (int i = 0; i < a.length - 1; i++)
    for (int j = 0; j < a.length - 1 - i; j++)
        if (a[j] > a[j + 1]) {
            int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;   // 交换
        }

手写它的意义在于练习边界(为什么内层是 - i、- 1),写完之后,实际开发请直接用标准库:

import java.util.Arrays;
Arrays.sort(a);                    // 基本类型:双轴快排,O(n log n)

这个分工本身就是一条工程价值观:算法要懂(知道它 O(n log n)、知道稳定性),代码用库(生产代码不手写排序)。String 数组的排序(String[] 按 Unicode 序)另有规则,涉及 Comparable 接口,第 8 章(面向对象下)讲。

5.3 查找:二分的前提是先有序

int idx = Arrays.binarySearch(a, 42);   // 要求 a 已升序!

二分查找 O(log n) 的前提是有序,对乱序数组直接 binarySearch 结果不可预期(这是 API 文档里的红色警告,不是学术讲究)。乱序先 Arrays.sort 再找,或老实用顺序遍历(O(n) 也不慢)。其他常用工具:Arrays.toString(a) 打印数组内容(直接 println 数组只会得到 [I@1b6d3586 这种「类型@哈希」的天书,新手第一坑)、Arrays.copyOf(a, n) 扩容拷贝、Arrays.fill(a, v) 填充。

5.4 二维数组:数组的数组

int[][] m = new int[3][4];         // 3 行 4 列
m[0][1] = 7;

Java 的二维数组是「数组的数组」:m 是长度 3 的数组,每个元素又是一个 int[](指针课第 5 章的「流派二」布局,数据结构课第 12 章的散装行)。这个语义的直接推论:每行长度可以不同(不规则数组):

int[][] tri = new int[3][];
tri[0] = new int[1];
tri[1] = new int[2];               // 三角形结构,第 0 行 1 列、第 1 行 2 列……
tri[2] = new int[3];

遍历嵌套两把增强 for 最顺手:for (int[] row : m) for (int x : row)。性能提示(数据结构课第 12 章的缓存行理论在 Java 同样成立):按行遍历(外层行内层列)比按列遍历快数倍,数值计算尽量行优先。

常见错误

println 直接打数组。得到 [I@1b6d3586,想看内容用 Arrays.toString(二维用 Arrays.deepToString)。
数组扩容试图 a.length = 10。length 是 final 的,改不了;扩容 = a = Arrays.copyOf(a, 10)(换了个新数组对象),或一开始就用第 9 章的 ArrayList。
交换数组元素时把引用当值拷。对象数组的「交换」交换的是引用,基本类型数组交换才是真的搬数据;排序自定义对象时用错比较语义,结果看着随机。
二分前忘排序。binarySearch 对乱序数组返回不可预期值(可能是负的插入点),文档警告不是摆设。

练习

动手:验证引用语义:int[] a = {1,2,3}; int[] b = a; b[0] = 99; 打印 a[0],解释为什么是 99;再用 Arrays.copyOf 修复成独立副本。
实现:手写选择排序和插入排序各一遍(数据结构课第 8 章),与 Arrays.sort 对 10 万随机数计时,记录三个数字。
实现:杨辉三角(不规则二维数组),打印前 10 行,练习「每行长度不同」的分配与遍历。
思考:Java 数组越界抛异常、C 数组越界是 UB(指针课第 14 章)。从计组课第 6 章「流水线的分支预测」和数据结构课第 12 章「缓存」的角度估算:每次数组访问多一次边界检查,代价大概是什么量级?JVM 的 JIT 有没有办法把这个检查优化掉(提示:常量边界 + 循环)。