（干货）入门期的基础算法
辗转相除法（求最大公约数）
辗转相除法基于如下原理：两个正整数a和b(a >= b)，他们的最大公约数等于a除以b的余数和b之间的最大公约数（迭代计算）。
程序实现为：
#include <stdio.h>
int main()
{int a,b, q;scanf("%d%d", &a,&b);while (q = a % b) {a = b;b = q;}printf("%d", b);return 0;
}
解析：设两个数a,b,假设a>=b,用a除以b,求得余数q.若q为0,则b为最大公约数；若q不等于0,则进行如下迭代：a=b,b=q,即原除数变为新的被除数,原余数变为新的除数
二分查找法
相比于遍历查找，二分查找的方法更加高效，但是该算法的使用前提是：静态查找表中的数据必须是有序的；
对于有序数组：
low和high分别指有序数组中的最大值和最小值；
mid是low和high的中间值，mid=（low+high）/2取整；
二分查找法通过比较中间值与目标查找值的大小来缩小查找范围；
程序实现：
#include <stdio.h>
int main ()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };int aim = 10;-----设定查找值为10；int low, high,mid;low = 0;----左端数值的下标high = sizeof(arr) / sizeof(arr[0])-1;----右端数值的下标while (low <= high){mid = (low + high) / 2;if (arr[mid] > aim)---将中间下标对应的值与目标值比较{high = mid - 1;}else if (arr[mid] < aim){low = mid+1;}else{printf("找到了，下标为%d", mid);break;}}if(low>high)printf("找不到！");return 0;
}
试除法（求素数）
程序实现：
#include <stdio.h>
#include <math.h>
int main()
{int a = 100, i;for (a = 101; a <= 200; a+=2){for (i = 2; i < sqrt(a); i++){if (a % i == 0)break;}if (i>sqrt(a)) printf("%d ", a);}return 0;
}
sqrt()函数是<math.h>中的库函数，用来计算一个数的平方根，返回类型为double浮点型，用%lf接收返回值
分析： 一个数n可以写成n=a*b的形式 且a,b至少有一个小于等于n的平方根，即sqrt(n);
一旦存在一个a,那么必定有一个b与之配对使得n=a*b成立； 所以我们从平方根处着手，遍历它之前的数，如果能找到n的非1的约数，则n不是素数；
这种方法比遍历2到n-1之间的数更加高效;
冒泡排序
冒泡排序（Bubble Sort）的基本思路是：对于一组要排序的元素列，依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面，如此继续，直到比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤，直至全部排序完成。
代码实现：
void Bubblesort(int sz, int arr[])
{int i=0, j=0;//i为冒泡排序的趟数，j为每一趟左右两个数比较的次数;for (i = 0; i < sz - 1; i++){int flag = 1;//假设进入循环时数组是有序的;for (j=0;j<sz-1-i;j++)if (arr[j] > arr[j + 1]){int tmp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = tmp;flag = 0;//假设此时数组无序；}if (1 == flag)//数组有序，退出循环；break;}
}
int main()
{int arr[] = { 1,4,6,8,9,3,2,5,7,10 };int sz = sizeof(arr) / sizeof(arr[0]);Bubblesort(sz,arr);int i = 0;for (i = 0; i < sz; i++)printf("%d ", arr[i]);//打印数组中的每一个元素return 0;
}
此时的输出结果为：
1 2 3 4 5 6 7 8 9 10
//作者定期分享C语言学习路上的经验，欢迎关注哦
（干货）入门期的基础算法
辗转相除法（求最大公约数）
辗转相除法基于如下原理：两个正整数a和b(a >= b)，他们的最大公约数等于a除以b的余数和b之间的最大公约数（迭代计算）。
程序实现为：
#include <stdio.h>
int main()
{int a,b, q;scanf("%d%d", &a,&b);while (q = a % b) {a = b;b = q;}printf("%d", b);return 0;
}
解析：设两个数a,b,假设a>=b,用a除以b,求得余数q.若q为0,则b为最大公约数；若q不等于0,则进行如下迭代：a=b,b=q,即原除数变为新的被除数,原余数变为新的除数
二分查找法
相比于遍历查找，二分查找的方法更加高效，但是该算法的使用前提是：静态查找表中的数据必须是有序的；
对于有序数组：
low和high分别指有序数组中的最大值和最小值；
mid是low和high的中间值，mid=（low+high）/2取整；
二分查找法通过比较中间值与目标查找值的大小来缩小查找范围；
程序实现：
#include <stdio.h>
int main ()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };int aim = 10;-----设定查找值为10；int low, high,mid;low = 0;----左端数值的下标high = sizeof(arr) / sizeof(arr[0])-1;----右端数值的下标while (low <= high){mid = (low + high) / 2;if (arr[mid] > aim)---将中间下标对应的值与目标值比较{high = mid - 1;}else if (arr[mid] < aim){low = mid+1;}else{printf("找到了，下标为%d", mid);break;}}if(low>high)printf("找不到！");return 0;
}
试除法（求素数）
程序实现：
#include <stdio.h>
#include <math.h>
int main()
{int a = 100, i;for (a = 101; a <= 200; a+=2){for (i = 2; i < sqrt(a); i++){if (a % i == 0)break;}if (i>sqrt(a)) printf("%d ", a);}return 0;
}
sqrt()函数是<math.h>中的库函数，用来计算一个数的平方根，返回类型为double浮点型，用%lf接收返回值
分析： 一个数n可以写成n=a*b的形式 且a,b至少有一个小于等于n的平方根，即sqrt(n);
一旦存在一个a,那么必定有一个b与之配对使得n=a*b成立； 所以我们从平方根处着手，遍历它之前的数，如果能找到n的非1的约数，则n不是素数；
这种方法比遍历2到n-1之间的数更加高效;
冒泡排序
冒泡排序（Bubble Sort）的基本思路是：对于一组要排序的元素列，依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面，如此继续，直到比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤，直至全部排序完成。
代码实现：
void Bubblesort(int sz, int arr[])
{int i=0, j=0;//i为冒泡排序的趟数，j为每一趟左右两个数比较的次数;for (i = 0; i < sz - 1; i++){int flag = 1;//假设进入循环时数组是有序的;for (j=0;j<sz-1-i;j++)if (arr[j] > arr[j + 1]){int tmp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = tmp;flag = 0;//假设此时数组无序；}if (1 == flag)//数组有序，退出循环；break;}
}
int main()
{int arr[] = { 1,4,6,8,9,3,2,5,7,10 };int sz = sizeof(arr) / sizeof(arr[0]);Bubblesort(sz,arr);int i = 0;for (i = 0; i < sz; i++)printf("%d ", arr[i]);//打印数组中的每一个元素return 0;
}
此时的输出结果为：
1 2 3 4 5 6 7 8 9 10
//作者定期分享C语言学习路上的经验，欢迎关注哦