微网站免,wordpress 积分下载,北京网站建设 案例,品牌建设青之见目录
一、冒泡法排序
1.1原理
1.2代码实现#xff08;以升序排序为例#xff09;
1.3逻辑
1.4分析
二、二分法查找
2.1原理
2.2代码实现
2.3逻辑
2.4算法效率分析
三、素数判断
3.1原理
3.2代码实现
3.3逻辑
3.4分析 一、冒泡法排序 1.1原理 冒泡排序…目录
一、冒泡法排序
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代码实现以升序排序为例 #includestdio.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次左右的除法运算来判断是否能被整除。 在实际应用中如果要判断更大范围的数是否为素数通常会采用更高效的算法比如埃拉托斯特尼筛法等这些算法可以大大提高判断素数的效率。
