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; // 先假设未找到，赋值为 -1while (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){// 如果能被整除，说明不是素数，标记为0isPrime = 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次左右的除法运算来判断是否能被整除。

在实际应用中，如果要判断更大范围的数是否为素数，通常会采用更高效的算法，比如埃拉托斯特尼筛法等，这些算法可以大大提高判断素数的效率。