C语言第九周课——经典算法
目录
一、冒泡法排序
1.1原理
1.2代码实现（以升序排序为例）
1.3逻辑
1.4分析
二、二分法查找
2.1原理
2.2代码实现
2.3逻辑
2.4算法效率分析
三、素数判断
3.1原理
3.2代码实现
3.3逻辑
3.4分析
一、冒泡法排序
1.1原理
- 冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
- 这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的顶端（升序排序的情况下），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样。
1.2代码实现（以升序排序为例）
#include<stdio.h> // 定义数组长度 #define SIZE 3 int main() { int arr[SIZE]; int i; // 从控制台输入数字到数组 printf("请输入%d个整数：\n", SIZE); for (i = 0; i < SIZE; i++) { scanf("%d", &arr[i]); } int n = SIZE; int h, j, temp; for (h = 0; h < n - 1; h++) { for (j = 0; j < n - h - 1; j++) { if (arr[j] > arr[j + 1]) { // 交换元素 temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } // 输出排序后的数组 printf("排序后的数组为：\n"); for (i = 0; i < SIZE; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }
1.3逻辑
在这段代码中：
- 在
main函数里，首先通过循环和scanf函数从控制台接收用户输入的数字，并存储到数组arr中。- 然后通过两层循环来对输入的数组进行冒泡排序。
- 最后再通过循环将排序后的数组元素输出到控制台。
1.4分析
- 时间复杂度分析
- 最好情况：当输入的数组已经是有序的情况下，冒泡排序只需要进行一轮比较，没有元素交换操作。此时时间复杂度为，其中
n是数组的长度。- 最坏情况：当输入的数组是逆序的情况下，需要进行
n-1轮比较，每一轮比较的次数逐渐减少，总的比较次数是，时间复杂度为。- 平均情况：时间复杂度也是，因为在平均情况下，数组元素的无序程度介于最好情况和最坏情况之间。
- 空间复杂度分析
- 冒泡排序是一种就地排序算法，它只需要一个额外的临时变量
temp来交换元素的位置，所以空间复杂度为。这意味着它在排序过程中不需要额外的大量存储空间，只需要对原始数组进行操作即可。
二、二分法查找
2.1原理
二分查找（Binary Search），也叫折半查找，是一种在有序数组中查找特定元素的高效算法。它的基本思想是：
- 每次比较中间元素与目标元素的值。
- 如果中间元素的值等于目标元素的值，那么就找到了目标元素，查找结束。
- 如果中间元素的值大于目标元素的值（因为是降序数组），则目标元素可能在数组的左半部分，所以下一次查找在左半部分继续进行。
- 如果中间元素的值小于目标元素的值，则目标元素可能在数组的右半部分，下一次查找就在右半部分继续进行。
通过不断地将查找范围缩小一半，直到找到目标元素或者确定目标元素不存在为止。
2.2代码实现
#include <stdio.h> // 定义数组长度 #define SIZE 10 int main() { int arr[SIZE] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; int target; // 从控制台输入要查找的目标数字 printf("请输入要查找的数字：\n"); scanf("%d", &target); int left = 0; int right = SIZE - 1; int result = -1; // 先假设未找到，赋值为 -1 while (left <= right) { // 计算中间元素的索引 int mid = left + (right - left) / 2; if (arr[mid] == target) { result = mid; break; // 找到目标元素，退出循环 } else if (arr[mid] < target) { right = mid - 1; } else { left = mid + 1; } } if (result!= -1) { printf("目标数字 %d 在数组中的索引为 %d\n", target, result); } else { printf("未找到目标数字 %d\n", target); } return 0; }
2.3逻辑
① 头文件包含
这行代码引入了标准输入输出头文件
stdio.h，使得程序能够使用printf、scanf等函数来进行控制台的输入输出操作。②数组定义与初始化
首先通过
#define指令定义了一个常量SIZE来表示数组的长度，这里设置为10。在
main函数内部，定义并初始化了一个名为arr的整数数组，数组元素按照降序排列，从10到1。这个数组是后续进行二分查找的对象。③目标数字输入
定义了一个整型变量
target，用于存储用户从控制台输入的要查找的目标数字。通过
printf函数输出提示信息，引导用户输入数字，然后使用scanf函数从控制台读取用户输入的整数，并将其存储到target变量中。④二分查找逻辑
首先初始化了三个整型变量：
left：用于表示查找范围的左边界，初始化为0，即数组的起始索引。
right：表示查找范围的右边界，初始化为SIZE - 1，也就是数组的最后一个元素的索引。
result：用于存储最终查找结果的索引，初始化为-1，表示先假设目标数字未找到。然后进入一个
while循环，只要left小于等于right，就说明查找范围还有效，继续进行查找操作：
在每次循环中，先通过公式
mid = left + (right - left) / 2计算出当前查找范围的中间元素的索引mid。这个公式的目的是为了避免整数溢出问题（相比于直接使用(left + right) / 2）。接着通过
if - else if - else语句来比较中间元素arr[mid]与目标元素target的大小关系：
如果
arr[mid]等于target，说明找到了目标元素，将mid赋值给result，并通过break语句退出循环。如果
arr[mid]小于target，由于数组是降序排列的，所以目标元素应该在当前中间元素的左边，因此将right更新为mid - 1，缩小查找范围到左半部分。如果
arr[mid]大于target，则目标元素应该在当前中间元素的右边，所以将left更新为mid + 1，缩小查找范围到右半部分。⑤查找结果输出
根据
result变量的值来判断是否找到目标数字。如果result不等于-1，说明找到了目标数字，通过printf函数输出目标数字及其在数组中的索引；如果result等于-1，则表示未找到目标数字，同样通过printf函数输出相应的提示信息。不过这里代码最后输出提示信息时有个小错误，printf("未找到目标数字 %d\n", darget);应该是printf("未找到目标数字 %d\n", target);，即把错误的darget修正为target。
2.4算法效率分析
二分查找算法的时间复杂度为O(log n)，其中
n是数组的长度。在每次循环中，查找范围都会缩小一半，所以经过对数级别的次数就能找到目标元素（如果存在的话）或者确定其不存在。相比于简单的顺序查找（时间复杂度为），二分查找在处理大型有序数组时效率更高。总体而言，这段代码实现了一个基本的二分查找功能，但需要注意修正输出提示信息时的拼写错误以确保代码的正确性。
三、素数判断
3.1原理
素数是指一个大于 1 且除了 1 和它自身外，不能被其他自然数整除的数。
①素数的定义及判断依据
根据素数的定义，要判断一个数
n是否为素数，需要检查它是否能被 2 到n - 1之间的任何数整除。如果在这个范围内都不能被整除，那么n就是素数；反之，如果能被其中某个数整除，那么n就不是素数。②程序实现思路
本程序通过两层循环来实现对 1 到 100 之内素数的判断：
外层循环负责遍历 1 到 100 之间的每一个整数，从 2 开始（因为 1 不是素数），依次对每个数进行素数判断操作。
对于外层循环遍历到的每一个整数，内层循环用于具体检查该数是否能被 2 到它自身减 1 之间的数整除。通过内层循环的检查结果来确定该数是否为素数。
3.2代码实现
#include <stdio.h> int main() { int i, j; printf("1到100之内的素数有：\n"); // 遍历1到100的数字 for (i = 2; i <= 100; i++) { // 假设当前数字i是素数 int isPrime = 1; // 检查i是否能被2到i-1之间的数字整除 for (j = 2; j < i; j++) { if (i % j == 0) { // 如果能被整除，说明不是素数，标记为0 isPrime = 0; break; } } // 如果isPrime为1，说明是素数，输出该数字 if (isPrime == 1) { printf("%d ", i); } } printf("\n"); return 0; }
3.3逻辑
在这个程序中：
- 在
main函数中，首先定义了两个整型变量i和j，分别用于外层循环和内层循环的计数。- 通过
printf函数输出提示信息，表示接下来要输出 1 到 100 之内的素数。- 然后是外层循环
for (i = 2; i <= 100; i++)，它会从 2 开始，每次递增 1，直到 100 为止，依次遍历这个范围内的每一个整数。对于每一个遍历到的整数i，都要进行是否为素数的判断。
- 外层循环
for (i = 2; i <= 100; i++)用于遍历从 2 到 100 的每一个整数。因为 1 不是素数，所以从 2 开始遍历。- 对于每一个要判断的整数
i，首先在内层循环之前假设它是素数，通过设置isPrime = 1来表示。- 内层循环
for (j = 2; j < i; j++)用于检查当前整数i是否能被 2 到i - 1之间的任何一个整数整除。如果能被整除（即i % j == 0），那么就说明i不是素数，此时将isPrime标记为 0，并通过break语句跳出内层循环，因为一旦确定不是素数就不需要再继续检查了。- 最后，当内层循环结束后，如果
isPrime的值仍然为 1，就说明i是素数，通过printf函数输出该数字。
3.4分析
这种判断素数的方法虽然简单直观，但效率相对较低。对于每一个要判断的数
n，都需要从 2 到n - 1进行遍历检查，其时间复杂度大致为O(n的2次方)（这里的n是要判断的数的范围，在本程序中是 100）。因为对于每个数都要进行n - 1次左右的除法运算来判断是否能被整除。在实际应用中，如果要判断更大范围的数是否为素数，通常会采用更高效的算法，比如埃拉托斯特尼筛法等，这些算法可以大大提高判断素数的效率。