一、数组基本操作算法

1. 数组逆置算法 时间复杂度：O(n)

#include <stdio.h>
int main(void) {
    int temp, idx, data[] = {1,2,3,4,5,6,7,8,9,0};
    int size = sizeof(data) / sizeof(data[0]);
    for (idx = 0; idx < size / 2; ++idx) {
        temp = data[idx];
        data[idx] = data[size - idx - 1];
        data[size - 1 - idx] = temp;
    }
    for (idx = 0; idx < size; ++idx) {
        printf("%d ", data[idx]);
    }
    putchar('\n');
    return 0;
}

2. 选择排序法 时间复杂度：O(n²)

核心思路：为每个位置挑选合适的元素。

#include <stdio.h>
int main(void) {
    int i, j, tmp, arr[] = {3,6,5,8,7,4,2,0,1,9};
    int len = sizeof(arr) / sizeof(arr[0]);
    for (i = 0; i < len - 1; ++i) {
        for (j = i + 1; j < len; ++j) {
            if (arr[i] > arr[j]) {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }
    for (i = 0; i < len; ++i)
        printf("%d,", arr[i]);
    printf("\b \n");
    return 0;
}

3. 冒泡排序法 时间复杂度：O(n²)

核心思路：相邻元素两两比较并交换。

#include <stdio.h>
int main(void) {
    int i, j, list[] = {3,4,6,1,9,7,2,0};
    int len = sizeof(list) / sizeof(list[0]);
    for (j = len - 1; j > 0; --j) {
        for (i = 0; i < j; ++i) {
            if (list[i] > list[i + 1]) {
                int swap = list[i];
                list[i] = list[i + 1];
                list[i + 1] = swap;
            }
        }
    }
    for (i = 0; i < len; ++i)
        printf("%d,", list[i]);
    printf("\b \n");
    return 0;
}

4. 直接插入排序法 时间复杂度：O(n²)

#include <stdio.h>
int main(void) {
    int i, j, nums[] = {4,6,1,7,2,9,0,3,8};
    int len = sizeof(nums) / sizeof(nums[0]);
    for (i = 1; i < len; ++i) {
        int temp = nums[i];
        j = i;
        while (j > 0 && nums[j - 1] > temp) {
            nums[j] = nums[j - 1];
            --j;
        }
        nums[j] = temp;
    }
    for (i = 0; i < len; ++i)
        printf("%d,", nums[i]);
    printf("\b \n");
    return 0;
}

5. 二分查找算法（折半搜索） 前提：数组已排序

#include <stdio.h>
int main() {
    int vals[] = {3,2,4,7,9,1,0,8};
    int i, j, len = sizeof(vals) / sizeof(vals[0]);
    // 首先使用插入排序使数组有序
    for (i = 1; i < len; ++i) {
        int key = vals[i];
        j = i;
        while (j > 0 && vals[j - 1] > key) {
            vals[j] = vals[j - 1];
            --j;
        }
        vals[j] = key;
    }
    int target = 7;
    int left = 0, right = len - 1, mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (vals[mid] < target)
            left = mid + 1;
        else if (vals[mid] > target)
            right = mid - 1;
        else
            break;
    }
    if (left <= right)
        printf("found\n");
    else
        printf("not found\n");
    return 0;
}

二、一维字符数组与字符串

1. 字符数组声明

2. 字符数组初始化方式

方式一：

花括号内的元素个数不能超过数组长度，否则越界。若初始化数据少于数组长度，剩余元素自动填充为'\0'（空字符）。

方式二：

方式三： 使用字符串字面量初始化

3. 字符串操作要点

• 有效长度：字符串中第一个'\0'之前的字符数量即为有效长度。例如，若某字符串前9个非空字符后第10个为'\0'，则其有效字符数为9。
• 结束标志：'\0'作为字符串结束符，循环判断时常用 s[i] != '\0'。
• 输入函数：
  • scanf("%s", s)：遇到空格、Tab或回车即停止读取，后续输入被忽略。
  • gets(s) / fgets(s, sizeof(s), stdin)：gets不含边界检查，使用时需注意缓冲区大小。
• 输出函数：
  • 逐字符遍历输出：printf("%c ", s[i])
  • 直接输出：puts(s)（参数为数组首地址）
  • 逐字符输出：putchar(s[i])