C 语言基础算法案例 - 从水仙花数到冒泡排序

本文通过三个经典案例，帮助理解 C 语言的基础算法：水仙花数判断、数组翻转、冒泡排序。

一、水仙花数

1.1 什么是水仙花数

水仙花数（Narcissistic number）：一个 n 位数等于其各位数字的 n 次幂之和。

对于三位数（也叫阿姆斯特朗数）：

1
2
3
4
153 = 1³ + 5³ + 3³ = 1 + 125 + 27 = 153
370 = 3³ + 7³ + 0³ = 27 + 343 + 0 = 370
371 = 3³ + 7³ + 1³ = 27 + 343 + 1 = 371
407 = 4³ + 0³ + 7³ = 64 + 0 + 343 = 407

1.2 取各位数字的方法

位数 公式 说明
个位 n / 1 % 10 取余数
十位 n / 10 % 10 先除10再取余
百位 n / 100 % 10 先除100再取余
千位 n / 1000 % 10 先除1000再取余 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
┌─────────────────────────────────────────────────────────────────────────┐
│                        数字分解示意图                                   │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│    以 123456 为例:                                                       │
│                                                                         │
│         1           2           3           4           5           6    │
│    ┌───┐       ┌───┐       ┌───┐       ┌───┐       ┌───┐       ┌───┐  │
│    │ 1 │   ×   │ 2 │   ×   │ 3 │   ×   │ 4 │   ×   │ 5 │   ×   │ 6 │  │
│    └───┘       └───┘       └───┘       └───┘       └───┘       └───┘  │
│      │           │           │           │           │           │     │
│      │          10          100        1000       10000      100000  │
│      └───────────┴───────────┴───────────┴───────────┴───────────┘     │
│                              ↓                                        │
│                      123456 = 100000×1 + 10000×2 + ...                 │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

1.3 完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>

int main() {
    printf("0-1000 以内的水仙花数:\n");
    printf("---------------------------\n");

    for (int i = 0; i < 1000; i++) {
        // 分解各位数字
        int baiWeiShu = i / 100 % 10;   // 百位数
        int shiWeiShu = i / 10 % 10;    // 十位数
        int geWeiShu = i / 1 % 10;      // 个位数

        // 计算各位数字的立方和
        int result = baiWeiShu * baiWeiShu * baiWeiShu +
                     shiWeiShu * shiWeiShu * shiWeiShu +
                     geWeiShu * geWeiShu * geWeiShu;

        // 判断是否为水仙花数
        if (i == result) {
            printf("水仙花数: %d\n", i);
        }
    }

    return 0;
}

1.4 运行结果

1
2
3
4
5
6
7
8
0-1000 以内的水仙花数:
---------------------------
水仙花数: 0
水仙花数: 1
水仙花数: 153
水仙花数: 370
水仙花数: 371
水仙花数: 407

二、数组翻转

2.1 算法思路

两头堵模型：使用两个指针，一个从头开始，一个从尾开始，交换元素后向中间移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
┌─────────────────────────────────────────────────────────────────────────┐
│                        数组翻转示意图                                   │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│  初始状态:                                                              │
│  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐              │
│  │  3  │  7  │ 79  │ 465 │  2  │ 65  │-346 │ 798 │  1  │  0  │              │
│  └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘              │
│    ▲                                                                   │
│    └───────────────────────────────────────────────────────────────▶     │
│                                                                         │
│  第1次交换: i=0, j=9                                                   │
│  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐              │
│  │  0  │  7  │ 79  │ 465 │  2  │ 65  │-346 │ 798 │  1  │  3  │              │
│  └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘              │
│         ▲                                                       ▲         │
│         └───────────────────────────────────────────────┘         │
│                                                                         │
│  第2次交换: i=1, j=8                                                   │
│  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐              │
│  │  0  │  1  │ 79  │ 465 │  2  │ 65  │-346 │ 798 │  7  │  3  │              │
│  └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘              │
│              ▲                                           ▲               │
│              └───────────────────────────────────────┘               │
│                                                                         │
│  ... 继续直到 i >= j                                                      │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

2.2 完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>

void ReverseArray() {
    int array[] = {3, 7, 79, 465, 2, 65, -346, 798, 1, 0};
    int size = sizeof(array) / sizeof(array[0]);

    printf("原始数组:\n");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n\n");

    // 数组翻转 - 两头堵模型
    for (int i = 0; i < size / 2; i++) {
        // 交换首尾元素
        int temp = array[i];
        array[i] = array[size - 1 - i];
        array[size - 1 - i] = temp;
    }

    printf("翻转后数组:\n");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

int main() {
    ReverseArray();
    return 0;
}

2.3 运行结果

1
2
3
4
5
原始数组:
3 7 79 465 2 65 -346 798 1 0

翻转后数组:
0 1 798 -346 65 2 465 79 7 3

三、冒泡排序

3.1 算法思路

冒泡排序：重复遍历数组，每次比较相邻元素，如果顺序错误就交换，直到没有需要交换的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
┌─────────────────────────────────────────────────────────────────────────┐
│                        冒泡排序示意图                                   │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│  原始数组: {7, 79, 465, 65, -345, -346, 798, 1, 0, 45}                     │
│                                                                         │
│  第1轮 (i=0):                                                           │
│  [7]  [79] [465] [65] [-345] [-346] [798] [1] [0]   [45]              │
│    ↓ 比较 → 交换 → 45 移动到末尾                                      │
│  结果: [7, 79, 65, 465, -345, -346, 1, 0, 45, 798]                     │
│                                                          ▲ 最大值已到位  │
│                                                                         │
│  第2轮 (i=1):                                                           │
│  [7]  [65] [79]  [465] [-345] [-346] [1] [0]   [45]   [798]          │
│  结果: [7, 65, 79, 465, -345, -346, 0, 1, 45, 798]                     │
│                                                    ▲ ▲ 最大两个值到位   │
│                                                                         │
│  第3轮 (i=2):                                                           │
│  结果: [7, 65, 79, -345, 465, -346, 0, 1, 45, 798]                     │
│                                                                         │
│  ... 继续直到全部排序完成                                                 │
│                                                                         │
│  最终结果: [-346, -345, 0, 1, 7, 45, 65, 79, 465, 798]                  │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

3.2 循环边界说明

轮数 (i) 内层循环范围 (j) 不参与比较的元素
0 0 ~ 8 最后 1 个
1 0 ~ 7 最后 2 个
2 0 ~ 6 最后 3 个
… … …
i 0 ~ (size-1-i-1) 最后 i+1 个

💡 关键：外层循环控制比较轮数，内层循环控制每轮比较的范围。

3.3 完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>

void BubbleSort() {
    int array[] = {7, 79, 465, 65, -345, -346, 798, 1, 0, 45};
    int size = sizeof(array) / sizeof(array[0]);

    printf("原始数组:\n");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n\n");

    // 冒泡排序
    // 外层循环: 控制比较轮数
    for (int i = 0; i < size - 1; i++) {
        // 内层循环: 相邻元素比较并交换
        for (int j = 0; j < size - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                // 交换相邻元素
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

    printf("排序后数组:\n");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

int main() {
    BubbleSort();
    return 0;
}

3.4 带调试输出的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>

void BubbleSortWithDebug() {
    int array[] = {7, 79, 465, 65, -345, -346, 798, 1, 0, 45};
    int size = sizeof(array) / sizeof(array[0]);

    // 外层循环
    for (int i = 0; i < size - 1; i++) {
        printf("\n===== 第 %d 轮比较 =====\n", i + 1);

        // 内层循环
        for (int j = 0; j < size - 1 - i; j++) {
            printf("比较 [%d](%d) 和 [%d](%d)",
                   j, array[j], j + 1, array[j + 1]);

            if (array[j] > array[j + 1]) {
                // 交换
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                printf(" → 交换!\n");
            } else {
                printf(" → 不交换\n");
            }
        }

        // 打印当前状态
        printf("当前状态: ");
        for (int k = 0; k < size; k++) {
            printf("%d ", array[k]);
        }
        printf("\n");
    }

    printf("\n===== 最终结果 =====\n");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

int main() {
    BubbleSortWithDebug();
    return 0;
}

3.5 运行结果

1
2
===== 最终结果 =====
-346 -345 0 1 7 45 65 79 465 798

四、算法复杂度分析

算法 时间复杂度 空间复杂度 稳定性
水仙花数 O(n) O(1) -
数组翻转 O(n) O(1) -
冒泡排序 O(n²) O(1) 稳定

4.1 冒泡排序优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 优化版: 如果某轮没有发生交换,说明已经排序完成
void OptimizedBubbleSort() {
    int array[] = {7, 79, 465, 65, -345, -346, 798, 1, 0, 45};
    int size = sizeof(array) / sizeof(array[0]);
    bool swapped;

    for (int i = 0; i < size - 1; i++) {
        swapped = false;
        for (int j = 0; j < size - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                swapped = true;
            }
        }
        // 如果没有发生交换,提前结束
        if (!swapped) break;
    }
}

五、总结

案例 核心知识点 关键技巧
水仙花数 取余 %、取整 / 运算 分解各位数字
数组翻转 双指针交换 i 从头开始, size-1-i 从尾开始
冒泡排序 嵌套循环、相邻比较 内层范围 size-1-i

💡 学习建议：

  • 理解算法的执行过程，可以画图帮助理解
  • 用调试输出观察每一步的变化
  • 从简单案例开始，逐步扩展到复杂场景
  • 注意循环边界条件，避免数组越界

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1487842110@qq.com