C语言基础篇（7）：数组进阶——排序、查找与字符数组

一、数组知识小结（回顾）

在进入进阶内容之前，先回顾数组的核心知识点：

1.1 为什么需要数组

当需要处理大量同类型数据时（如统计全班成绩），逐个定义变量不现实，数组提供了一种批量管理变量的方式。

1.2 数组定义

数据类型 数组名[数组长度]; int a[10]; // 定义了一个包含 10 个 int 型元素的数组

1.3 数组的三大特点

1.4 数组元素的引用

通过下标访问数组中的具体元素：

a[0] = 1; // 下标从 0 开始 a[1] = 2;

1.5 给值方式

// 全部初始化 int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 部分初始化——前面的元素依次赋值，后面默认为 0 int a[10] = {1, 2, 3, 4, 5}; // 不初始化——数组中是随机值（垃圾值） int a[10]; // 初始化成全 0 int a[10] = {0}; int a[10] = {}; // 初始化器，默认给 0 // 初始化时省略长度，由初始化值个数推算 int a[] = {1, 2, 3, 4}; // 数组长度为 4

注意：数组不能整体赋值

int a[10]; a = {1, 2, 3, 4, 5}; // ❌ 错误！必须逐个元素赋值 a[0] = 2; // ✅ 正确

二、排序算法

2.1 选择排序

核心思想：给合适的位置选择合适的数。

算法步骤：外层循环控制位置，内层循环从剩余元素中找到合适（最小或最大）的数放到当前位置。

代码实现（升序）：

int i, j; for (i = 0; i < n - 1; i++) // 外层：控制位置 { for (j = i + 1; j < n; j++) // 内层：从 i+1 开始找数 { if (a[j] < a[i]) // 如果找到更小的 { int t = a[i]; // 交换 a[i] = a[j]; a[j] = t; } } }

时间复杂度分析：

i = 0 时，内层循环 n-1 次 i = 1 时，内层循环 n-2 次 i = 2 时，内层循环 n-3 次 ... i = n-2 时，内层循环 1 次 总计：1 + 2 + 3 + ... + (n-1) = n(n-1)/2 = n²/2 - n/2

时间复杂度：O(n²)（用最高次项来反映增长趋势）

2.2 冒泡排序

核心思想：相邻两个元素两两比较，小的往前放，大的往后放，像气泡一样浮到末尾。

代码实现（升序）：

int i, j; for (i = 1; i < n; ++i) // 外层：控制趟数 { for (j = 0; j < n - i; ++j) // 内层：相邻比较 { if (a[j] > a[j + 1]) // 前面比后面大，就交换 { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } } }

时间复杂度：O(n²)

2.3 插入排序

核心思想：将数据插入到已有的有序序列中，通过和已排序的序列进行比较，找到合适的位置插入。

场景理解：想象打扑克牌时，每摸一张新牌，就把它插入到手中已排好序的牌的正确位置。

代码实现（升序）：

int i, j; for (i = 1; i < n; ++i) { int t = a[i]; // 取出当前要插入的元素 j = i; while (j > 0 && t < a[j - 1]) // 在已排序序列中从后往前找位置 { a[j] = a[j - 1]; // 比 t 大的元素往后挪 --j; } a[j] = t; // 插入到正确位置 }

时间复杂度分析：

i = 1 时，最多比较 1 次 i = 2 时，最多比较 2 次 i = 3 时，最多比较 3 次 ... i = n-1 时，最多比较 n-1 次

时间复杂度：O(n²)

2.4 三种排序对比

三、查找算法：二分查找

3.1 前提条件

数据必须是有序的（排好序的数组）。

3.2 核心思想

每次找到中间位置，将中间位置的值和要找的值比较：

• 中间值>目标值 → 目标在左半部分
• 中间值<目标值 → 目标在右半部分
• 中间值==目标值 → 找到了

3.3 过程图示

以在有序数组中查找值1为例：

数组：1 2 3 4 5 6 7 8 9 10 第 1 次：中间值 = 5，5 > 1，往左找 第 2 次：中间值 = 2，2 > 1，往左找 第 3 次：中间值 = 1，1 == 1，找到！

3.4 代码实现

int begin = 0, end = n - 1, mid; int target; // 要查找的目标值 int found = -1; // -1 表示未找到 while (begin <= end) { mid = (begin + end) / 2; // 中间位置 if (a[mid] > target) { end = mid - 1; // 目标在左半部分 } else if (a[mid] < target) { begin = mid + 1; // 目标在右半部分 } else { found = mid; // 找到了，记录位置 break; } } if (begin <= end) { // 找到了 printf("找到了，位置是 %d\n", found); } else { // 没找到 printf("没找到\n"); }

3.5 时间复杂度

四、一维字符型数组与字符串

4.1 字符数组的定义

char s[10]; // 10 个 char 元素的数组，大小 10 字节

字符型数组和 int 型数组本质上没有太大区别，主要是用来处理字符数据。

4.2 字符串的存储方式

C 语言中用双引号表示字符串常量："hello"

字符串在内存中按字符数组方式存储：

char s[10] = "hello";

字符串结束标志：\0。字符串的长度是\0前面有效字符的个数。

4.3 字符数组的初始化

// 用字符串常量初始化 char s[10] = "hello"; // 用字符列表初始化（部分初始化，后面补 0） char s[10] = {'h', 'e', 'l', 'l', 'o'}; // 等价于 'h','e','l','l','o','\0',0,0,0,0 // 省略长度，由初始化值推算（自动包含 \0） char s[] = "hello"; // 数组长度为 6（5个字符 + 1个\0）

4.4 字符串与数组的关系

• 字符数组是存放字符串的容器。
• 处理字符串时，更关心字符串什么时候结束（\0），而不是数组什么时候结束。
• 因此数组长度显得不那么重要，\0才是关键。

4.5 获取字符串长度：strlen

#include <string.h> size_t strlen(const char *s);

• 功能：计算字符串长度（\0前面有效字符的个数）。
• 注意：strlen和sizeof不同——strlen不算\0，sizeof算整个数组大小。

char s[10] = "hello"; strlen(s); // 返回 5（'h','e','l','l','o'，不算 \0） sizeof(s); // 返回 10（整个数组的大小）

4.6 字符串复制：strcpy

#include <string.h> char *strcpy(char *dest, const char *src);

• 功能：将src中的字符串复制到dest中。
• 参数：
  • src— 字符串源（数组名或字符串常量）。
  • dest— 目标数组名或存放字符串的空间地址。
• 返回值：返回dest。

char s1[10] = "hello"; char s2[10] = "world"; strcpy(s1, s2); // s1 变为 "world"

4.7 字符串拼接：strcat

#include <string.h> char *strcat(char *dest, const char *src);

• 功能：将src中的字符串拼接到dest末尾。
• 参数：
  • src— 字符串源（数组名或字符串常量）。
  • dest— 目标数组名或存放字符串的空间地址。
• 返回值：返回dest。

char s1[20] = "hello"; char s2[10] = "world"; strcat(s1, s2); // s1 变为 "helloworld"

拼接思路：

1. 1.定位到\0的位置。
2. 2.从\0位置开始依次复制src中的字符。
3. 3.最后补上\0。

五、总结