C: 实战：数组与函数综合

Q: 冒泡排序和选择排序哪个更好？

两者时间复杂度都是O(n^2)，但冒泡排序有提前终止优化，最好情况O(n)。实际效率差别不大，都不适合大数据量。

Q: 二分查找前提条件是什么？

数组必须已排序且支持随机访问。链表不能用二分查找，因为无法O(1)访问中间元素。

Q: 字符串反转能用库函数实现吗？

C标准库没有直接的反转函数。C++的 <algorithm> 有 std::reverse ，C需要自己实现。

学了再多招式，不上擂台永远只是纸上谈兵。这章把数组、函数、指针融会贯通，用四个实战项目检验你真正的功力。

1. 项目一：冒泡排序

冒泡排序是最基础的排序算法。思路是反复遍历数组，比较相邻元素，如果顺序错误就交换，直到没有交换发生为止。每一轮遍历会把当前最大值"冒泡"到末尾。

(1) 算法步骤

从第一个元素开始，依次比较相邻两个元素
如果前者大于后者，交换它们
一轮结束后，最大值到达正确位置
对剩余部分重复，直到全部有序

(2) 实现

#include <stdio.h>

void bubble_sort(int *arr, int len) {
    int i, j;
    int swapped;

    for (i = 0; i < len - 1; i++) {
        swapped = 0;
        for (j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
}

void print_array(const int *arr, int len) {
    int i;
    for (i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(void) {
    int data[] = {64, 34, 25, 12, 22, 11, 90};
    int len = sizeof(data) / sizeof(data[0]);

    printf("排序前: ");
    print_array(data, len);

    bubble_sort(data, len);

    printf("排序后: ");
    print_array(data, len);

    return 0;
}

TEXT 📖 仅展示

排序前: 64 34 25 12 22 11 90
排序后: 11 12 22 25 34 64 90

swapped标志优化：如果某一轮没有发生任何交换，说明数组已经有序，提前终止。最好情况下（已排序数组）时间复杂度降为O(n)。

💡 冒泡排序平均和最差时间复杂度O(n^2)，仅适合小数据量或教学演示。实际项目用qsort。

▶ 示例

用冒泡排序对成绩降序排名：

#include <stdio.h>

void sort_desc(int *arr, int len) {
    int i, j, swapped;
    for (i = 0; i < len - 1; i++) {
        swapped = 0;
        for (j = 0; j < len - 1 - i; j++) {
            if (arr[j] < arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
}

int main(void) {
    int scores[] = {85, 92, 78, 95, 88};
    int len = sizeof(scores) / sizeof(scores[0]);
    int i;

    sort_desc(scores, len);
    printf("排名: ");
    for (i = 0; i < len; i++) {
        printf("%d ", scores[i]);
    }
    printf("\n");
    return 0;
}

▶ 试一试

TEXT 📖 仅展示

排名: 95 92 88 85 78

降序只需将比较条件从>改为<。

2. 项目二：二分查找

二分查找在已排序数组中高效定位目标值，每次将搜索范围缩小一半。

(1) 算法步骤

设定搜索范围[low, high]
取中间位置mid = (low + high) / 2
如果arr[mid]等于目标，找到
如果arr[mid]小于目标，搜索右半部分
如果arr[mid]大于目标，搜索左半部分
范围缩小到空仍未找到，则不存在

(2) 实现

#include <stdio.h>

int binary_search(const int *arr, int len, int target) {
    int low = 0;
    int high = len - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;
}

int main(void) {
    int data[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 78};
    int len = sizeof(data) / sizeof(data[0]);
    int targets[] = {23, 7, 78, 1};
    int num = sizeof(targets) / sizeof(targets[0]);
    int i;

    for (i = 0; i < num; i++) {
        int pos = binary_search(data, len, targets[i]);
        if (pos >= 0) {
            printf("%d 在位置 %d\n", targets[i], pos);
        } else {
            printf("%d 不存在\n", targets[i]);
        }
    }
    return 0;
}

TEXT 📖 仅展示

23 在位置 5
7 不存在
78 在位置 9
1 不存在

💡 用low + (high - low) / 2而非(low + high) / 2避免整数溢出。这是二分查找的经典细节。

时间复杂度O(log n)，10亿个元素最多只需30次比较。

▶ 示例

查找第一个大于等于目标的元素位置（下界查找）：

#include <stdio.h>

int lower_bound(const int *arr, int len, int target) {
    int low = 0;
    int high = len;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

int main(void) {
    int data[] = {1, 3, 3, 5, 7, 7, 7, 9, 11};
    int len = sizeof(data) / sizeof(data[0]);
    int pos = lower_bound(data, len, 7);
    printf("第一个 >= 7 在位置 %d，值=%d\n", pos, data[pos]);
    return 0;
}

▶ 试一试

TEXT 📖 仅展示

第一个 >= 7 在位置 4，值=7

下界查找在算法竞赛和STL中极为常用。

3. 项目三：字符串反转

将字符串前后字符互换，如"hello"变为"olleh"。使用双指针法原地操作，不需要额外数组。

(1) 实现

#include <stdio.h>
#include <string.h>

void str_reverse(char *s) {
    char *left = s;
    char *right = s + strlen(s) - 1;

    while (left < right) {
        char temp = *left;
        *left = *right;
        *right = temp;
        left++;
        right--;
    }
}

int main(void) {
    char s1[] = "Hello World";
    char s2[] = "ABCDE";
    char s3[] = "racecar";

    str_reverse(s1);
    str_reverse(s2);
    str_reverse(s3);

    printf("%s\n", s1);
    printf("%s\n", s2);
    printf("%s\n", s3);

    return 0;
}

TEXT 📖 仅展示

dlroW olleH
EDCBA
racecar

注意必须用字符数组（可修改），不能用指针指向字符串常量。

▶ 示例

判断回文字符串（跳过非字母数字，忽略大小写）：

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int is_palindrome(const char *s) {
    const char *left = s;
    const char *right = s + strlen(s) - 1;
    while (left < right) {
        while (left < right && !isalnum((unsigned char)*left)) left++;
        while (left < right && !isalnum((unsigned char)*right)) right--;
        if (tolower((unsigned char)*left) != tolower((unsigned char)*right)) {
            return 0;
        }
        left++;
        right--;
    }
    return 1;
}

int main(void) {
    printf("%d\n", is_palindrome("racecar"));
    printf("%d\n", is_palindrome("hello"));
    printf("%d\n", is_palindrome("A man a plan a canal Panama"));
    return 0;
}

▶ 试一试

TEXT 📖 仅展示

1
0
1

4. 项目四：字符频率统计

统计字符串中每个字符出现的次数，是文本分析的基础操作。

(1) 实现

#include <stdio.h>
#include <string.h>

void char_freq(const char *s, int *freq, int size) {
    int i;
    for (i = 0; i < size; i++) freq[i] = 0;
    while (*s != '\0') {
        unsigned char ch = (unsigned char)*s;
        if (ch < (unsigned)size) freq[ch]++;
        s++;
    }
}

int main(void) {
    char text[] = "Hello World!";
    int freq[256] = {0};
    int i;

    char_freq(text, freq, 256);

    for (i = 32; i < 127; i++) {
        if (freq[i] > 0) printf("'%c': %d  ", i, freq[i]);
    }
    printf("\n");
    return 0;
}

TEXT 📖 仅展示

' ': 1  '!': 1  'H': 1  'W': 1  'd': 1  'e': 1  'l': 3  'o': 2  'r': 1

利用ASCII值作为数组下标，一次遍历完成统计。256个槽位覆盖所有8位字符。

▶ 示例

统计字母频率并找出最高频字母：

#include <stdio.h>
#include <ctype.h>
#include <string.h>

void letter_freq(const char *s, int *freq) {
    int i;
    for (i = 0; i < 26; i++) freq[i] = 0;
    while (*s != '\0') {
        if (isalpha((unsigned char)*s)) {
            freq[tolower((unsigned char)*s) - 'a']++;
        }
        s++;
    }
}

char find_max(const int *freq, int size) {
    int max_idx = 0;
    int i;
    for (i = 1; i < size; i++) {
        if (freq[i] > freq[max_idx]) max_idx = i;
    }
    return 'a' + max_idx;
}

int main(void) {
    const char *text = "The quick brown fox jumps over the lazy dog";
    int freq[26];
    letter_freq(text, freq);
    char max_ch = find_max(freq, 26);
    printf("最高频字母: %c (%d次)\n", max_ch, freq[max_ch - 'a']);
    return 0;
}

▶ 试一试

TEXT 📖 仅展示

最高频字母: o (4次)

❓ 常见问题

Q 冒泡排序和选择排序哪个更好？

A 两者时间复杂度都是O(n^2)，但冒泡排序有提前终止优化，最好情况O(n)。实际效率差别不大，都不适合大数据量。

Q 二分查找前提条件是什么？

A 数组必须已排序且支持随机访问。链表不能用二分查找，因为无法O(1)访问中间元素。

Q 字符串反转能用库函数实现吗？

A C标准库没有直接的反转函数。C++的<algorithm>有std::reverse，C需要自己实现。

Q 频率统计为什么用256大小的数组？

A unsigned char范围0-255共256个值。用字符ASCII值做下标，256个槽位覆盖所有可能字符，一次遍历即可完成统计。

📖 小节

冒泡排序通过相邻元素交换实现排序，swapped标志可提前终止
二分查找要求有序数组，O(log n)效率远优于线性查找
双指针法原地反转字符串，空间复杂度O(1)
字符频率统计利用ASCII值做数组下标，一次遍历完成
综合项目体现数组存储、函数封装、指针操作三大核心能力

📝 作业

改进冒泡排序：实现一个函数，既能升序也能降序排序，通过函数指针参数控制比较方式。
实现二分查找的递归版本int bin_search_rec(const int *arr, int low, int high, int target)。
编写字符频率统计的增强版：读取用户输入的一行文本，输出频率最高的前3个字符及其次数。

Web-Tutorial 技术团队

由多位开发者共同维护的编程教程平台。每篇教程由对应领域的开发者编写和审核，确保内容准确可靠。如发现任何问题，欢迎向我们反馈。

关于我们

C: 实战：数组与函数综合

1. 项目一：冒泡排序

(1) 算法步骤

(2) 实现

▶ 示例

2. 项目二：二分查找

(1) 算法步骤

(2) 实现

▶ 示例

3. 项目三：字符串反转

(1) 实现

▶ 示例

4. 项目四：字符频率统计

(1) 实现

▶ 示例

❓ 常见问题

📖 小节

📝 作业

🙏 帮我们做得更好