第 5 章 · 数组

5.1 数组的定义与遍历

数组是定长、同类型元素的集合，在 Java 中数组本身是对象。

int[] a = new int[5];          // 默认 0
int[] b = {1, 2, 3, 4, 5};     // 静态初始化
int n = a.length;              // 长度是属性，不是方法

for (int i = 0; i < a.length; i++) { }   // 下标遍历
for (int x : a) { }                       // 增强 for 遍历

• 下标从 0 开始；越界访问抛 ArrayIndexOutOfBoundsException。
• a.length 是只读属性；数组创建后长度不可变。

对比 C：C 数组越界是未定义行为（可能读到脏数据甚至崩溃），Java 越界抛异常、安全可控。Java 数组自带长度属性，C 必须手动传递数组长度。

5.2 排序

冒泡排序：相邻两两比较交换，每一轮把最大（小）元素“冒”到末尾，O(n²)。

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;
        }

插入排序：把元素插入到已排序子序列的正确位置，接近有序时接近 O(n)。

实际开发直接用 Arrays.sort(a)（底层是双轴快排，基本类型 O(n log n)）。

5.3 查找

• 顺序查找：从头遍历，O(n)。
• 二分查找：要求有序，每次折半，O(log n)。可用 Arrays.binarySearch(a, key)。

5.4 二维数组

二维数组是“数组的数组”，每行长度可不同（不规则数组）：

int[][] m = new int[3][4];
m[0][1] = 7;
for (int[] row : m)
    for (int x : row) { }

5.5 与其他语言对比

• C/C++：数组退化为指针、无边界信息；Java 数组是对象，携带长度、越界检查，代价是少了指针算术的灵活性。
• Python：用 list，可动态扩容、元素可异构，功能更强但性能与内存开销更大；Java 数组固定大小、同类型，性能更高。