C 语言指针系列（三）：数组名、指针访问与冒泡排序

前两篇文章我们搞懂了指针的基本操作和 const/野指针/传址调用的实战技巧。但有一个话题我一直"绕着走"——指针和数组到底是什么关系？ 你可能已经隐约感觉到它们之间有某种奇妙联系：数组的元素可以用指针遍历，数组名似乎能直接赋值给指针变量……但它们又不是同一个东西。

这篇文章正面回答这个困扰无数 C 语言学习者的难题。核心结论其实就一句话：数组名在绝大多数情况下等于首元素地址——然后我们会深入分析那两个著名的例外。有了这些基础，你会真正理解为什么 arr[3] 和 3[arr] 居然等价（对，你没看错），以及为什么数组传给函数后就"变小"了。这一篇还会补齐数组指针（int (*p)[N]）这个前两篇一直没展开的家族成员——它是理解二维数组的关键钥匙。最后用冒泡排序来一次实战沉淀，顺势进入二级指针和指针数组的世界。

数组名的本质

先直接用代码验证那个核心结论：

#include <stdio.h>
 
int main()
{
    int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
 
    printf("&arr[0] = %p\n", &arr[0]);  // 首元素的地址
    printf("arr     = %p\n", arr);      // 数组名直接打印
 
    return 0;
}
// 输出（示例）：
// &arr[0] = 0077F820
// arr     = 0077F820   ← 完全一样！

两个值一模一样。在 C 语言绝大多数上下文中，数组名就是数组首元素的地址。这意味着 int *p = arr; 等价于 int *p = &arr[0];——你可以直接把数组名当作一个指向首元素的指针值来使用。

但注意措辞：数组名是"首元素地址的值"，不等于"数组名就是指针变量"。这两者的区别很关键，后面专门讲。

但如果数组名总是等于首元素地址，那这段代码怎么解释？

#include <stdio.h>
 
int main()
{
    int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    printf("%zu\n", sizeof(arr));    // 输出 40（不是 4 或 8！）
    return 0;
}

如果 arr 就是一个指针，sizeof(arr) 应该输出指针变量的大小（4 或 8 字节）。但实际输出了 40——也就是 10 × sizeof(int)，整个数组的大小。数组名并非任何时候都是指针——它有且仅有两个例外：

这两个例外非常重要——尤其是 sizeof，它解释了为什么我们在函数外部能用 sizeof(arr)/sizeof(arr[0]) 算数组长度，但在函数内部不行。

一个容易让人困惑的现象是 arr 和 &arr 的数值相同但类型不同：

#include <stdio.h>
 
int main()
{
    int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
 
    printf("&arr[0]   = %p\n", (void*)&arr[0]);
    printf("&arr[0]+1 = %p\n", (void*)(&arr[0] + 1));  // +4字节
 
    printf("arr       = %p\n", (void*)arr);
    printf("arr+1     = %p\n", (void*)(arr + 1));        // +4字节
 
    printf("&arr      = %p\n", (void*)&arr);
    printf("&arr+1    = %p\n", (void*)(&arr + 1));        // +40字节！
 
    return 0;
}
// 典型输出：
// &arr[0]   = 0077F820
// &arr[0]+1 = 0077F824   ← 差 4
// arr       = 0077F820
// arr+1     = 0077F824   ← 差 4
// &arr      = 0077F820
// &arr+1    = 0077F848   ← 差 40！

内存图中能看得很清楚：

    arr[0]  arr[1]  arr[2]  ...  arr[9]
    ┌──────┬──────┬──────┬──┬──────┐
    │   1  │   2  │   3  │..│  10  │  ← 共40字节
    └──────┴──────┴──────┴──┴──────┘
    ↑                            ↑
    arr = &arr[0]               arr+10 = 数组尾后
    = &arr                      &arr+1 指向整个数组之后

    arr+1  → 跳过 1个元素 → 移动 4字节  → arr[1]的地址
    &arr+1 → 跳过整个数组 → 移动 40字节 → 越过整个数组

• arr 的类型是 int*，指向一个 int，所以 +1 跳 4 字节
• &arr 的类型是 int (*)[10]，指向"包含10个int的数组"，所以 +1 跳 40 字节
• 数值相同但类型不同，运算行为不同——这就是第一篇讲的"指针类型决定步长"的经典体现。

int (*)[10] 这种"指向数组的指针"就是数组指针，它在数组传参和二维数组里是主角，稍后单独开一节。

再补充一个"数组名不是变量"的推论：数组名是一个不可修改的地址常量。所以下面的写法全是编译错误：

int arr[10];
arr++;        // ❌ 数组名不是左值，不能自增
arr = arr;    // ❌ 数组名不可赋值

为什么？因为数组名不是变量——它没有自己的存储空间（不像指针变量那样占 8 字节）。编译器对 arr 的处理是"知道它代表数组起始地址"这个信息，而不是"读取一个存着地址的变量"。所以你能 p = arr;（把地址值拷贝给指针变量 p），但不能 arr = p;（数组名没有"值存储"可写）。

思考题（数组名的本质）

1. sizeof(arr) 和 sizeof(&arr) 各是多少？（40 和 8——一个是整个数组，一个是指针变量）
2. 为什么 arr++ 非法而 p++ 合法？（数组名是地址常量，不是可修改的左值；指针变量是左值）
3. &arr + 1 指向哪里？（整个数组之后的那个位置，距离 arr 40 字节）

参考答案与详解（数组名的本质）

1. sizeof(arr) vs sizeof(&arr)：sizeof(arr) 中数组名单独出现，表示整个数组，结果是 10 × sizeof(int) = 40；sizeof(&arr) 中 &arr 的类型是数组指针 int (*)[10]，是一个指针，结果是指针大小（64 位下 8、32 位下 4）。一个算"数组大小"，一个算"指针大小"，这正是"两个例外"的直接体现（sizeof(数组名)、&数组名）。
2. arr++ 非法而 p++ 合法：数组名 arr 是一个地址常量（不可修改的左值），常量不能自增自减、不能赋值 arr = ...；而指针变量 p 是真正有存储空间、可以改写的左值，所以 p++ 合法。根源是数组名不是变量——编译器只把 arr 当作"数组起始地址"这个信息，并不会为它在一级内存中提供一个可写的"指针存储单元"。p = arr;（地址值拷贝给指针变量）可以，arr = p;（写数组名）不行。
3. &arr + 1 指向哪：&arr 的类型是 int (*)[10]，步长 = sizeof(int[10]) = 40 字节，所以 &arr + 1 指向整个数组之后的那个位置（数组尾后，距 arr 40 字节）。它和"arr 首元素"数值相同，但类型不同、+1 跳的字节数完全不同——这是"指针类型决定步长"的最直观证明。

使用指针访问数组

有了"数组名 = 首元素地址"的前提，用指针遍历数组就非常自然了：

#include <stdio.h>
 
int main()
{
    int arr[10] = {0};
    int *p = arr;                          // p指向首元素
    int sz = sizeof(arr) / sizeof(arr[0]); // 计算元素个数
    int i;
 
    // 用指针输入
    for (i = 0; i < sz; i++)
    {
        scanf("%d", p + i);   // p+i 是第i个元素的地址
        // 等价于 scanf("%d", arr + i);
    }
 
    // 用指针输出
    for (i = 0; i < sz; i++)
    {
        printf("%d ", *(p + i));  // 解引用拿到值
    }
    printf("\n");
 
    return 0;
}

这里有一层更深的关系：p[i] 和 *(p+i) 在编译器眼中完全等价。C 语言标准规定，E1[E2] 等价于 *((E1) + (E2))。这意味着四种写法效果相同：

#include <stdio.h>
 
int main()
{
    int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int *p = arr;
    int i;
 
    for (i = 0; i < 10; i++) printf("%d ", arr[i]);     // 传统下标
    printf("\n");
 
    for (i = 0; i < 10; i++) printf("%d ", *(arr + i)); // 指针+偏移
    printf("\n");
 
    for (i = 0; i < 10; i++) printf("%d ", p[i]);       // 指针当下标用
    printf("\n");
 
    for (i = 0; i < 10; i++) printf("%d ", *(p + i));   // 指针+偏移
    printf("\n");
 
    return 0;
}
// 全部输出：1 2 3 4 5 6 7 8 9 10

这个等价关系还有一个"副作用"：因为 arr[i] 等价于 *(arr + i)，而加法是可交换的，所以 *(i + arr) 也等价——于是 i[arr] 居然是合法的！

#include <stdio.h>
 
int main()
{
    int arr[10] = {1, 2, 3, 4, 5};
    printf("%d\n", 3[arr]);   // 输出 4！因为 *(3+arr) == *(arr+3)
    printf("%d\n", arr[3]);   // 输出 4
    return 0;
}

别在实际代码里写 3[arr]——这只说明了一点：下标操作的本质就是不折不扣的指针运算。

不过，数组名和指针变量之间有一个重要区别：数组名不能移动，指针变量可以。

int arr[5] = {1, 2, 3, 4, 5};
int *p = arr;
 
arr++;     // ❌ 编译错误！arr 是地址常量
p++;       // ✅ p 指向 arr[1]
 
// 等价的下标写法也有差别：
// arr[i] 中的 arr 是"固定的基地址"
// p[i] 中的 p 是"可以移动的基地址"——p 一旦 ++，p[0] 就不再是 arr[0]

表格里最关键的一行是"类型"：arr 的类型是"5 个 int 的数组"，只是在表达式中退化（decay）成首元素地址；p 的类型本来就是指针。这是 C 语言里"数组"和"指针"最本质的分野。

思考题（指针访问数组）

1. p[i]、*(p+i)、i[p] 三者什么关系？（完全等价，都是 *(p+i)）
2. 循环遍历完数组后，p 指向哪？（数组尾后位置，再 *p 就是未定义行为）
3. 为什么 scanf("%d", p + i) 不需要 &？（p+i 本身就是一个地址，scanf 要的就是地址）

参考答案与详解（指针访问数组）

1. p[i]、*(p+i)、i[p] 完全等价：C 标准规定下标运算 E1[E2] 就是 *((E1)+(E2))，所以三者分别展开成 *(p+i)、*(p+i)、*(i+p)——由于加法可交换，i+p 和 p+i 相同，三者指向同一内存且值相同，是同一个东西的三种写法。这也是 3[arr] 会编译通过的原因。
2. 遍历完数组后 p 指向哪：循环让 p 从 arr[0] 一直 ++ 到 arr[sz]（即数组尾后/one-past-the-end）时才退出循环。尾后位置合法用于比较，但绝不能解引用——再 *p 就是未定义行为（读取了不存在的元素）。所以"遍历完"的指针是悬在边界外的，必须复位或不要再碰它。
3. scanf("%d", p + i) 不用 &：p + i 经过指针运算，结果本身就是"第 i 个元素的地址"（类型 int*），而 scanf("%d", ...) 要的正是这个地址。如果画蛇添足写成 scanf("%d", &(p + i)) 反而错了——那会取 "p+i 这个临时地址值" 的地址，类型变成 int**，语义完全不对。

一维数组传参的本质

如果你理解了上面的内容，这里有一个经典困惑会迎刃而解：

#include <stdio.h>
 
void test(int arr[])
{
    int sz = sizeof(arr) / sizeof(arr[0]);
    printf("函数内部: sz = %d\n", sz);
}
 
int main()
{
    int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int sz = sizeof(arr) / sizeof(arr[0]);
    printf("main中   : sz = %d\n", sz);    // 输出 10
    test(arr);                               // 输出 1 或 2
    return 0;
}

为什么 test 函数内部的 sizeof(arr) 不是 40？因为数组传参的本质是传递首元素的地址。函数参数中 void test(int arr[]) 和 void test(int *arr) 完全等价。数组作为参数时，编译器会自动把它退化为指针。函数内部的 sizeof(arr) 计算的不是数组大小，而是指针变量的大小：

main 的栈帧
┌─────────────────┐
│ arr ┌──┬──┬──┬──┤  整个数组，sizeof(arr)=40
│     │1 │2 │..│10│
│     └──┴──┴──┴──┤
└────────┬────────┘
         │ 传递的是首元素地址（指针值）
         ▼
test 的栈帧
┌─────────────────┐
│ arr = 指针值    │  sizeof(arr) = 4或8 (指针变量大小)
└─────────────────┘

很多初学者会在函数内部用 sizeof(arr) 来算数组长度——这是最常见的指针错误之一。正确的做法是把数组长度作为独立参数传入：

#include <stdio.h>
 
void print_array(int arr[], int sz)
{
    int i;
    for (i = 0; i < sz; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
 
int main()
{
    int arr[] = {1, 2, 3, 4, 5};
    int sz = sizeof(arr) / sizeof(arr[0]);  // 在main中计算
    print_array(arr, sz);                    // 传入数组和大小
    return 0;
}

这里有个推论：因为形参 arr 实际是指针，所以函数内 arr[i] = 5 会直接修改调用者的数组——数组传参是传址调用。这也是为什么不需要 & 就能在函数里改数组：传进去的本来就是地址。写函数时想"只读不改"，就用 const int arr[] 做形参，让编译器帮你把关。

形参三种写法完全等价（编译后都是指针）：

void f1(int arr[], int n);      // 最常见的写法
void f2(int arr[10], int n);    // 写 10 没用，编译器忽略维度
void f3(int *arr, int n);       // 本质形态

void f2(int arr[10]) 里的 10 纯属"装饰"——编译器会无视它。初学者看到 int arr[10] 以为数组大小被记住了，这是幻觉。

思考题（一维数组传参）

1. 函数内部 sizeof(arr) 为什么是 8（64 位）？（形参 arr 已退化为指针）
2. 怎么才能让函数知道数组有几个元素？（把长度作为第二个参数传入）
3. 为什么 void f(int arr[10]) 里写 10 是没用的？（形参退化，数组维度信息丢失）

参考答案与详解（一维数组传参）

1. 函数内 sizeof(arr) 为什么是 8（64 位）：形参里写的 int arr[] 其实被编译器"改写"成了 int *arr（数组名形参一律退化为指针）。所以函数里的 arr 是一个指针变量，sizeof(arr) 算的是指针大小（64 位下 8 字节），而不是数组大小。这就是为什么在函数里用 sizeof(arr)/sizeof(arr[0]) 算不出元素个数。
2. 怎么让函数知道元素个数：既然形参退化成指针、丢失了长度信息，那唯一的办法就是把长度作为独立参数显式传进去：void f(int arr[], int sz)。调用时先在外部（那里 sizeof(arr) 还能拿到真实数组大小）算好 sz 再传入。这是 C 里所有"数组 + 长度"成对出现的函数（如 qsort）的通行做法。
3. void f(int arr[10]) 里的 10 是"装饰"：无论你写成 int arr[]、int arr[10] 还是 int arr[999]，作为形参都会被编译器降级成 int *arr，那个"10"连校验都不会做（传更大的数组也毫无预警）。它只给人阅读时一种心理暗示，编译器完全忽略。真正靠谱的是显式传 sz，并在文档里说清"数组实际大小由 sz 决定"。

数组指针

前两篇我们一直在用 int *p 这种"指向元素的指针"，现在介绍它的兄弟——数组指针：指向"整个数组"的指针。声明时括号是关键：

int *p1[5];      // p1 是数组：5 个 int* 元素      —— 指针数组
int (*p2)[5];    // p2 是指针：指向 int[5] 数组    —— 数组指针

解析规则：[] 的优先级高于 *。所以 int *p1[5] 中 p1 先和 [5] 结合，p1 是数组；int (*p2)[5] 中括号改变了优先级，p2 先和 * 结合，p2 是指针。

数组指针最经典的初始化对象就是 &arr——还记得吗，&arr 的类型正是 int (*)[10]：

#include <stdio.h>
 
int main()
{
    int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
 
    // p是指针，指向一个包含10个int的数组
    int (*p)[10] = &arr;   // 注意：是 &arr，不是 arr
 
    // arr      → int*       （首元素地址）
    // &arr     → int(*)[10] （整个数组的地址）
    // 类型必须匹配！
 
    printf("arr     = %p\n", (void*)arr);
    printf("&arr    = %p\n", (void*)&arr);
    printf("p       = %p\n", (void*)p);
    // 三个值相同，但类型不同
 
    int i;
    for (i = 0; i < 10; i++)
    {
        // *p 得到整个数组 → 再[i]下标访问
        printf("%d ", (*p)[i]);
    }
    printf("\n");
 
    return 0;
}

类型解析：

int   (*p)   [10]   = &arr;
 │      │      │
 │      │      └── p指向的数组有10个元素
 │      └── p是数组指针变量名，*表示指针
 └── p指向的数组的元素类型是int

几个关键点：

1. *p 得到整个数组。p 指向数组，解引用 *p 就是那个数组本身；而数组在表达式中退化为首元素地址，所以 *p 的值等于 arr。于是 (*p)[i] 和 arr[i] 完全等价。
2. p + 1 跳过整个数组（40 字节）。因为 p 指向的类型是 int[10]，步长 = sizeof(int[10])。
3. 括号不能丢：*p[i] 会被解析成 *(p[i])（因为 [] 优先级高于 *），语义完全错了。

数组指针最核心的应用是二维数组的传参——二维数组的每一行是一个一维数组，二维数组的数组名就是"第一行的地址"，类型是数组指针。这个在下一篇文章会专门展开。这里先掌握一维场景：数组指针 = 装着"整个数组地址"的指针，解引用后得到数组，+1 跳过整个数组。

数组指针和指针数组是一对双胞胎，务必分清楚：

思考题（数组指针）

1. int (*p)[10] 中 p+1 跳过多少字节？（40）
2. *p 和 p[0] 等价吗？（等价，都是 *(p+0)——第一个数组本身）
3. 为什么 int (*p)[5] = arr;（arr 是 int[10]）会报警告？（类型不匹配：int(*)[10] 不能赋给 int(*)[5]）

参考答案与详解（数组指针）

1. p + 1 跳过多少字节：p 的类型是 int (*)[10]，指向"包含 10 个 int 的数组"，所以一步长 = sizeof(int[10]) = 10 × 4 = 40 字节。p + 1 与 p 相差 40 字节。这是"指针加一的步长 = 指向类型的大小"这条铁律在数组指针上的直接延展。
2. *p 和 p[0] 等价：二者都是 *(p + 0)，即解引用 p 得到 p 指向的那个数组（int[10]）。在表达式中，这个数组会退化为首元素地址，值等于 arr。所以 *p 和 p[0] 不仅等价，而且都退化成指向 arr[0] 的一级指针。
3. int (*p)[5] = arr 报警告：arr 是 int[10]，它的 &arr 类型是 int (*)[10]；而语句右侧的 arr 单独出现时退化为 int*。要装进 int (*)[5]（指向恰好 5 个 int 的数组）这个变量，无论是 int* 还是 int (*)[10] 都类型不匹配，编译器报 "incompatible pointer type"。数组指针的初始值必须来自同一类型的数组地址：int (*p)[10] = &arr;（注意是 &arr 而不是 arr）。若 p 声明成 [5] 却去接一个 10 元素数组的地址，步长维度都对不上，是错误的。

冒泡排序

搞清了数组名、指针访问和传参退化，我们来一个实战练习——手写冒泡排序。冒泡排序的思想很简单：两两比较相邻元素，如果顺序不对就交换，每一轮把最大的元素"浮"到最后。

#include <stdio.h>
 
// 冒泡排序：arr是数组首地址，sz是元素个数
void bubble_sort(int arr[], int sz)
{
    int i, j;
    for (i = 0; i < sz - 1; i++)
    {
        // 每趟后末尾i个元素已经排好，不需要再比较
        for (j = 0; j < sz - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])       // 相邻比较
            {
                int tmp = arr[j];           // 交换
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}
 
int main()
{
    int arr[] = {3, 1, 7, 5, 8, 9, 0, 2, 4, 6};
    int sz = sizeof(arr) / sizeof(arr[0]);
    int i;
 
    printf("排序前: ");
    for (i = 0; i < sz; i++)
        printf("%d ", arr[i]);
    printf("\n");
 
    bubble_sort(arr, sz);
 
    printf("排序后: ");
    for (i = 0; i < sz; i++)
        printf("%d ", arr[i]);
    printf("\n");
 
    return 0;
}
// 输出：
// 排序前: 3 1 7 5 8 9 0 2 4 6
// 排序后: 0 1 2 3 4 5 6 7 8 9

注意 bubble_sort 的形参 int arr[] 是"传址"，所以函数内部交换 arr[j] 和 arr[j+1] 直接改的就是 main 里的数组——这就是上一篇文章讲的"数组传参天然传址"。sizeof(arr)/sizeof(arr[0]) 必须在 main 里算好再传进来，函数里算一定是错的（因为形参退化成指针了）。

排序过程可视化（以 {3,1,7,5} 为例）：

第1趟（sz=4, i=0, j<3）：
  j=0:  3>1 ✓ → 交换  [1,3,7,5]
  j=1:  3>7 ✗ → 不动  [1,3,7,5]
  j=2:  7>5 ✓ → 交换  [1,3,5,7]  ← 最大值7到位

第2趟（i=1, j<2）：
  j=0:  1>3 ✗ → 不动  [1,3,5,7]
  j=1:  3>5 ✗ → 不动  [1,3,5,7]  ← 次大值5到位

第3趟（i=2, j<1）：
  j=0:  1>3 ✗ → 不动  [1,3,5,7]  ← 已完成，但循环仍执行

观察这个表格能总结出两件事：外层循环 i 控制"已经排好了多少个"（最后 i 个元素已到位）；内层循环 j 只比较 sz - i - 1 对——因为末尾 i 个元素已经是最大的了，不用再碰。整个算法的时间复杂度是 O(n²)，空间复杂度 O(1)。

如果某一趟没有发生任何交换，说明数组已经完全有序，可以用一个 flag 提前结束：

#include <stdio.h>
 
void bubble_sort_v2(int arr[], int sz)
{
    int i, j;
    for (i = 0; i < sz - 1; i++)
    {
        int flag = 1;   // 假设本趟已经有序
 
        for (j = 0; j < sz - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                flag = 0;                   // 发生了交换，说明无序
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
 
        if (flag == 1)   // 一趟下来没交换 → 已经有序
            break;
    }
}
 
int main()
{
    int arr[] = {1, 2, 3, 5, 4};  // 只有最后两个元素无序
    int sz = sizeof(arr) / sizeof(arr[0]);
    int i;
 
    bubble_sort_v2(arr, sz);
 
    for (i = 0; i < sz; i++)
        printf("%d ", arr[i]);
    printf("\n");
 
    return 0;
}
// 对于 {1,2,3,5,4}：
// 第1趟交换了(5和4) → flag=0 → 继续
// 第2趟没有交换 → flag=1 → break → 提前结束

这个优化在数组基本有序时效果显著，最好情况降到 O(n)。但别忘了时间复杂度本质仍是 O(n²)——冒泡排序是教学价值大于工程价值。实际项目里排序直接调标准库 qsort（第四篇文章会讲）。

顺带一提：写冒泡排序还有一个容易忽略的细节——内层循环的边界 j < sz - i - 1。如果写成 j < sz - i，当 j + 1 == sz - i 时，arr[j+1] 可能访问到"已经排好序的最大值"，虽然不越界但多了一次无意义比较；如果写 j < sz - 1 会多做很多轮。理解边界来源：每一轮要比较的对数 = 剩余未排序元素数 - 1。

思考题（冒泡排序）

1. 冒泡排序最好、最坏、平均时间复杂度？（O(n)、O(n²)、O(n²)，最好情况需要 flag 优化）
2. 为什么内层循环的上界是 sz - i - 1？（末尾 i 个元素已排好，不需要再参与比较）
3. 冒泡排序稳定吗？（稳定：相等元素不会交换相对顺序——条件是比较用 > 而不是 >=）

参考答案与详解（冒泡排序）

1. 时间复杂度三种情况：最坏情况（数组完全逆序）和平均情况都是 O(n²)（双层循环，比较次数约 n²/2）；最好情况（数组已有序）在加了 flag 提前退出的前提下能降到 O(n)（第一趟扫描发现一次交换都没有就 break）。注意：不加 flag 优化的经典写法即使数组有序也要老老实实跑满两层循环，最好情况也是 O(n²)。
2. 为什么内层上界是 sz - i - 1：外层循环每过一趟 i，就会把当前未排序区间的最大值"冒"到最末尾。所以第 i+1 趟开始时，末尾的 i 个元素已经是最大的、排好的，无需再参与比较。剩余未序元素有 sz - i 个，相邻要比较的对数是 sz - i - 1，所以内层 j 从 0 到 sz - i - 1（不包含），保证 arr[j]、arr[j+1] 都在未排区内。
3. 稳定性：稳定。因为相邻比较用的是 >（严格大于）才交换，相等元素 arr[j] == arr[j+1] 时不满足 >，不会交换，因此相等元素的相对先后顺序保持不变。如果错误地写成 >=，相等元素也会被交换，排序就不再稳定了。

二级指针

指针变量本身也是变量——这意味着它也有自己的地址。存放"指针变量地址"的变量，就是二级指针：

#include <stdio.h>
 
int main()
{
    int a = 10;
    int *pa = &a;       // 一级指针：存放a的地址
    int **ppa = &pa;    // 二级指针：存放pa的地址
 
    printf("&a  = %p\n", (void*)&a);
    printf("pa  = %p  (pa指向a)\n", (void*)pa);
    printf("&pa = %p  (pa自己的地址)\n", (void*)&pa);
    printf("ppa = %p  (ppa指向pa)\n", (void*)ppa);
 
    return 0;
}

内存布局：

         栈区
    ┌────────────┐
    │ a  = 10    │ ← 地址: 0x100
    └────────────┘
          ↑ pa指向
    ┌────────────┐
    │ pa = 0x100 │ ← 地址: 0x200
    └────────────┘
          ↑ ppa指向
    ┌────────────┐
    │ ppa= 0x200 │ ← 地址: 0x300
    └────────────┘

运算规律很直观：*ppa == pa，**ppa == *pa == a。每解引用一次就向"数据"方向走一层：

#include <stdio.h>
 
int main()
{
    int a = 10;
    int *pa = &a;
    int **ppa = &pa;
 
    printf("**ppa = %d\n", **ppa);   // 输出 10
 
    **ppa = 30;                      // 通过二级指针修改a
    printf("a = %d\n", a);           // 输出 30
 
    int b = 20;
    *ppa = &b;       // 等价于 pa = &b，修改一级指针的指向
    printf("*pa = %d\n", *pa);       // 输出 20 (现在pa指向b)
 
    return 0;
}

什么时候需要二级指针？回顾上一篇文章的结论：C 只有传值调用。如果你要在函数里修改调用者的指针变量本身（不只是修改指针指向的数据），就需要把"指针变量的地址"传进去——也就是传二级指针。最典型的场景是动态内存分配后回传指针：

#include <stdio.h>
#include <stdlib.h>
 
// 在函数里给指针分配内存并"带回去"
// 必须传二级指针：因为要修改调用者的指针变量
int InitPtr(int **pp, int value)
{
    *pp = (int *)malloc(sizeof(int));   // 分配堆内存
    if (*pp == NULL)
        return -1;                       // 分配失败
    **pp = value;                        // 通过二级指针写入
    return 0;
}
 
int main()
{
    int *p = NULL;
    if (InitPtr(&p, 100) == 0)
        printf("*p = %d\n", *p);        // 输出 100
    free(p);                             // 用完释放
    p = NULL;                            // 释放后立刻置空，避免悬空指针（呼应前文纪律）
    return 0;
}

如果只传一级指针 void InitPtr(int *pp, ...)，函数内部 pp = malloc(...) 只是修改了形参的指向，调用者的 p 还是 NULL——这正是"传值调用"的坑。函数要改"指针变量"就传"指针的地址"，即二级指针，这个规律可以一路推广到 n 级指针：要改几级的对象，就传几级 + 1 的指针。

思考题（二级指针）

1. *ppa 的类型是什么？**ppa 呢？（int * 和 int）
2. 为什么 InitPtr 要传 int **？（要修改调用者的 int * 变量，需要它的地址）
3. int ***ppp 是几级指针？怎么用？（三级指针，***ppp 是最终数据；实际工程极少用到三级以上）

参考答案与详解（二级指针）

1. *ppa 与 **ppa 的类型：ppa 是 int **，解引用一次 *ppa 得到的是它指向的 pa——而 pa 的类型是 int *，所以 *ppa 的类型是 int *；再解引用一次 **ppa 得到 *pa，也就是 a，类型是 int。规律：每解引用一层，"级数"降一级，最终降到最底层的数据类型。
2. 为什么 InitPtr 要传 int **：传址调用的守则是"函数要修改几级的对象，就传几级指针"。InitPtr 的意图是修改调用者的 int * 指针变量 p（给它分配堆地址），所以要传 p 的地址，即 int **。如果只传 int *，函数内 pp = malloc(...) 只是改了形参 pp 的指向、main 里的 p 依然是 NULL——这正是"传值调用"的坑：形参怎么改都影响不到实参。
3. int ***ppp 三级指针：***ppp 才是最终数据。实际工程里三级以上极为罕见（二三级就基本够用），因为代数层次越多越难读、越易错。它的存在场景多是"要改二级指针变量"（比如给 char** 数组扩容后回传），但绝大多数时候可被结构体、指针数组等替代。面试中更多是考"你能否正确解引用到几层"而非让你真去写三级指针。

指针数组

类比一下：整型数组 int arr[5] 存放 5 个 int，字符数组 char str[10] 存放 10 个 char——那指针数组 int *parr[5] 就是存放 5 个 int*（指针）。

#include <stdio.h>
 
int main()
{
    int a = 10, b = 20, c = 30;
 
    // parr是数组，每个元素是一个int*类型的指针
    int *parr[3] = {&a, &b, &c};
    int i;
 
    for (i = 0; i < 3; i++)
    {
        // parr[i] 是一个指针
        // *parr[i] 解引用拿到指向的值
        printf("%d ", *parr[i]);
    }
    printf("\n");
 
    return 0;
}
// 输出：10 20 30

内存布局：

    parr[0]    parr[1]    parr[2]
    ┌──────┐  ┌──────┐  ┌──────┐
    │ &a   │  │ &b   │  │ &c   │
    └──┬───┘  └──┬───┘  └──┬───┘
       │         │         │
       ▼         ▼         ▼
    ┌─────┐  ┌─────┐  ┌─────┐
    │a=10 │  │b=20 │  │c=30 │
    └─────┘  └─────┘  └─────┘

指针数组最常见的用途是模拟不规则的"二维数组"：

#include <stdio.h>
 
int main()
{
    int row1[] = {1, 2, 3, 4, 5};
    int row2[] = {2, 3, 4, 5, 6};
    int row3[] = {3, 4, 5, 6, 7};
 
    int *parr[3] = {row1, row2, row3};
    int i, j;
 
    for (i = 0; i < 3; i++)
    {
        for (j = 0; j < 5; j++)
        {
            printf("%d ", parr[i][j]);  // 等价于 *(parr[i] + j)
        }
        printf("\n");
    }
 
    return 0;
}
// 输出：
// 1 2 3 4 5
// 2 3 4 5 6
// 3 4 5 6 7

parr[i][j] 为什么能工作？parr[i] 取出第 i 个指针（指向第 i 行的首元素），parr[i][j] 等价于 *(parr[i] + j)——在该行内偏移 j 个元素。注意这里数组名 row1 等也发生了退化（从"数组"变成"首元素地址"），所以 int *parr[3] = {row1, row2, row3}; 类型才匹配。

需要特别注意：指针数组模拟的"二维数组"中，每一行是独立的数组，在内存中不一定连续。而真正的 int arr[3][5] 在内存中是连成一片的。两者还有一个关键区别：指针数组的"行"可以长度不同（比如 char *names[] = {"Tom", "Jerry", "Alice"} 每个字符串长度不一），真二维数组的每行长度必须相同。这种"每行不等长"的数据结构，用指针数组存是标准解法。

另外很多人会混淆指针数组和数组指针——int *p[10] 是数组（元素是指针），int (*p)[10] 是指针（指向数组）。[] 的优先级高于 *，所以要改变优先级必须加括号。

思考题（指针数组）

1. int *parr[3] 里 parr[1] 的类型？（int *）
2. parr[i][j] 等价于什么？（*(parr[i] + j)）
3. 指针数组模拟的二维数组和真二维数组在内存布局上的区别？（前者各行不连续，后者连续）

参考答案与详解（指针数组）

1. parr[1] 的类型：int *parr[3] 的声明里，[] 优先级高于 *，所以 parr 先和 [3] 结合成一个"3 个元素的数组"，每个元素的类型是 int *。因此 parr[1] 取出的是数组下标 1 的元素，类型是 int *（一个指向 int 的指针）。
2. parr[i][j] 等价于：parr[i] 先取出第 i 个元素（一个 int*，指向第 i 行），再对它做下标运算 [j]，即 *(parr[i] + j)——在第 i 行内偏移 j 个元素后解引用。所以 parr[i][j] 等价于 *(parr[i] + j)，常用等价写法还有 *(*(parr + i) + j)。
3. 两种"二维"的内存布局差异：真正的二维数组 int arr[3][5] 在内存里是一整块连续的 3×5=15 个 int（行与行首尾相接）；而指针数组 int *parr[3] 只是"三个指针连续"，每个指针指向的"行"（一维数组）是各自独立分配、行与行之间不保证连续，甚至可以长度不同。这是二者的本质区别，也是指针数组适合实现"每行不等长的字符串数组"的原因。

这篇文章里我们正面攻克了"数组名到底是不是指针"这个经典困惑——答案是：绝大多数情况下是，但 sizeof 和 & 是两个关键例外。这个理解是后续所有指针高级内容的基础。我们还补齐了数组指针（指向整个数组的指针）这一块拼图，掌握了二维数组传参的秘密武器，并用冒泡排序做了一次传址调用+数组名的综合实战，最后用二级指针和指针数组打开了"指针的指针"和"数组的指针元素"两扇新门。

在进入下一篇之前，做两个小练习验收：

练习 1：用指针数组实现：定义三个字符串 "hello"、"world"、"!"，把它们放进 char *strs[3]，用循环打印每个字符串及其长度。

练习 2：定义 int arr[3][4]，用 int (*p)[4] 遍历打印所有元素，并打印 p、p+1、p+2 的地址，验证每行跳 16 字节。

练习 1 参考答案

#include <stdio.h>
#include <string.h>
 
int main()
{
    // strs 是指针数组：3 个元素都是 char*，分别指向三个字符串常量
    char *strs[3] = {"hello", "world", "!"};
    int i;
 
    for (i = 0; i < 3; i++)
    {
        printf("str = %-6s  长度 = %zu\n", strs[i], strlen(strs[i]));
    }
 
    return 0;
}
// 输出：
// str = hello   长度 = 5
// str = world   长度 = 5
// str = !       长度 = 1

解析："hello" 是字符串常量，strs[0] 保存的是它的首字符地址而非整个字符串。strs[i] 是 char*（地址），printf("%s", ...) 从该地址一直打印到 \0；strlen(strs[i]) 统计 \0 前的字符个数。这正是本文"指针数组 + 字符串常量"的经典组合（与 part4 的 char *week[] 同一形态）。

练习 2 参考答案

#include <stdio.h>
 
int main()
{
    int arr[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
    // p 是数组指针：指向"包含 4 个 int 的数组"
    int (*p)[4] = arr;   // arr 是二维数组名，即第一行的地址，类型 int(*)[4]
    int i, j;
 
    for (i = 0; i < 3; i++)
    {
        for (j = 0; j < 4; j++)
        {
            printf("%d ", (*p)[j]);   // *p 得到第 i 行（一维数组），再下标访问
        }
        printf("\n");
        p++;   // p 向后跳一行 → 实际跳过 sizeof(int[4]) = 16 字节
    }
 
    // 若要逐行打印地址验证"每行跳 16 字节"：
    // int (*q)[4] = arr;
    // printf("%p\n", (void*)q);   // 第一行地址
    // printf("%p\n", (void*)(q+1)); // 第二行地址，比上一行大 16
    // printf("%p\n", (void*)(q+2)); // 第三行地址，比上一行大 16
    return 0;
}

解析：p = arr 中 arr 退化为"第一行的地址"（类型 int (*)[4]），正好匹配 p。内层 (*p)[j] 先用 *p 解引用把"这一行"取出来（得到 int[4]，再退化为 int*），再 [j] 取第 j 个元素；内层循环结束后 p++ 让 p 移动到下一行。因为 p 指向的类型是 int[4]，所以 p+1 跳 sizeof(int[4]) = 16 字节——这就是"数组指针步长 = 整个行的大小"的直接验证。

下一篇，我们将进入一个全新的领域——函数指针和回调函数。你会发现函数也有地址，你可以把函数作为参数传递，C 标准库中大名鼎鼎的 qsort 正是依赖这个机制实现的。期待和你一起探索！

本文基于C语言教学课件《第13讲：深入理解指针(3)》的内容框架撰写，所有代码示例均在GCC/MinGW环境下验证通过。