数组操作

数组是 C 语言中最基础的数据结构，掌握常见的数组操作——遍历、查找、排序、反转、复制——是编写高效程序的基础。这些操作也是面试和算法竞赛中的常客，理解它们的实现原理有助于选择合适的数据结构和算法。

遍历

int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);

/* 下标遍历 */
for (int i = 0; i < n; i++)
    printf("%d ", arr[i]);

/* 指针遍历 */
for (int *p = arr; p < arr + n; p++)
    printf("%d ", *p);

查找

线性查找：

int linear_search(const int arr[], int n, int target)
{
    for (int i = 0; i < n; i++)
        if (arr[i] == target)
            return i;           /* 找到，返回索引 */
    return -1;                  /* 未找到 */
}

时间复杂度 O(n)。

二分查找（要求数组有序）：

int binary_search(const int arr[], int n, int target)
{
    int left = 0, right = n - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;    /* 避免溢出 */
        
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    
    return -1;
}

时间复杂度 O(log n)。

排序

冒泡排序：

void bubble_sort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

时间复杂度 O(n²)。

快速排序（使用标准库）：

#include <stdlib.h>

/* 比较函数 */
int compare_int(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}

int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};
qsort(arr, sizeof(arr) / sizeof(arr[0]), sizeof(int), compare_int);

qsort 是 C 标准库提供的快速排序实现。

反转

void reverse(int arr[], int n)
{
    for (int i = 0; i < n / 2; i++) {
        int temp = arr[i];
        arr[i] = arr[n - 1 - i];
        arr[n - 1 - i] = temp;
    }
}

复制

#include <string.h>

/* 方法 1：循环 */
for (int i = 0; i < n; i++)
    dest[i] = src[i];

/* 方法 2：memcpy */
memcpy(dest, src, n * sizeof(int));

/* 方法 3：memmove（源和目的重叠时安全） */
memmove(dest, src, n * sizeof(int));

memcpy 在源和目的重叠时行为未定义，memmove 可以安全处理重叠。

插入和删除

数组的插入和删除需要移动元素，效率较低：

/* 在位置 pos 插入 value */
void insert(int arr[], int *n, int capacity, int pos, int value)
{
    if (*n >= capacity || pos < 0 || pos > *n)
        return;                 /* 错误处理 */
    
    for (int i = *n; i > pos; i--)
        arr[i] = arr[i - 1];    /* 后移元素 */
    
    arr[pos] = value;
    (*n)++;
}

/* 删除位置 pos 的元素 */
void delete(int arr[], int *n, int pos)
{
    if (pos < 0 || pos >= *n)
        return;
    
    for (int i = pos; i < *n - 1; i++)
        arr[i] = arr[i + 1];    /* 前移元素 */
    
    (*n)--;
}

时间复杂度 O(n)。频繁插入删除的场景应考虑链表。

最大值和最小值

int find_max(const int arr[], int n)
{
    if (n <= 0) return 0;       /* 错误处理 */
    
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max)
            max = arr[i];
    return max;
}

int find_min(const int arr[], int n)
{
    if (n <= 0) return 0;
    
    int min = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] < min)
            min = arr[i];
    return min;
}

常见错误

数组大小计算错误：

void func(int arr[])
{
    int n = sizeof(arr) / sizeof(arr[0]);   /* 错误！ */
}

排序比较函数错误：

/* 错误：返回差值可能溢出 */
int compare(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;           /* 溢出！ */
}

/* 正确 */
int compare(const void *a, const void *b)
{
    int x = *(int *)a;
    int y = *(int *)b;
    if (x < y) return -1;
    if (x > y) return 1;
    return 0;
}

memcpy 重叠：

int arr[] = {1, 2, 3, 4, 5};
memcpy(arr + 2, arr, 3 * sizeof(int));      /* 未定义行为：重叠！ */

/* 正确 */
memmove(arr + 2, arr, 3 * sizeof(int));     /* 安全 */

最佳实践

数组操作始终知道数组大小
排序使用 qsort，不要自己实现简单排序（除非学习目的）
复制用 memcpy（不重叠）或 memmove（可能重叠）
频繁插入删除考虑链表或动态数组
查找有序数组用二分查找
始终处理空数组和越界情况