当前位置：首页 > news >正文

关于我、重生到500年前凭借C语言改变世界科技vlog.14——常见C语言算法

news 2024/11/4 15:35:30

文章目录

1.冒泡排序
2.二分查找
3.转移表
希望读者们多多三连支持
小编会继续更新
你们的鼓励就是我前进的动力！

根据当前所学C语言知识，对前面知识进行及时的总结巩固，出了这么一篇 vlog 介绍当前所学知识能遇到的常见算法，这些算法是在C数据结构初阶常用的一些算法，重要性不言而喻，本章将用简单易懂的语言带领读者深入理解

1.冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止

核心思想：两两元素进行比较交换

基本原理
1.比较相邻的元素，如果第一个比第二个大（假设是按照升序排序，若为降序则相反），就交换它们两个
2.对每一对相邻元素作同样的操作，从开始第一对到结尾的最后一对，这样在经过第一轮比较后，最大的元素就会 “浮” 到数列的末尾
3.针对所有的元素重复以上的步骤，除了最后已经排好序的元素（因为每一轮都会把当前未排序部分的最大元素移到最后，所以每轮结束后末尾的元素数量会增加，这些元素就不需要再参与后续排序了）
4.持续重复上述过程，直到整个数列都按照要求的顺序排列好

理论知识介绍完，举个例子或许你就完全明白了
假设我们有一个数组 [5, 4, 3, 2, 1] 要进行升序排序：

第一轮排序
1.比较第 1 个元素 5 和第 2 个元素 4，因为 5 > 4，所以交换它们，数组变为 [4, 5, 3, 2, 1]
2.接着比较第 2 个元素 5 和第 3 个元素 3，因为 5 > 3，交换后数组变为 [4, 3, 5, 2, 1]
3.再比较第 3 个元素 5 和第 4 个元素 2，交换得到 [4, 3, 2, 5, 1]
4.最后比较第 4 个元素 5 和第 5 个元素 1，交换后数组变为 [4, 3, 2, 1, 5]。此时第一轮排序结束，最大的元素 5 已经 “浮” 到了数组的末尾

第二轮排序
1.对除了最后一个元素 5 之外的数组部分 [4, 3, 2, 1] 进行同样操作
2.先比较第 1 个元素 4 和第 2 个元素 3，交换得 [3, 4, 2, 1]
3.再比较第 4 个元素 4 和第 3 个元素 2，交换得 [3, 2, 4, 1]
4.最后比较第 3 个元素 4 和第 4 个元素 1，交换得 [3, 2, 1, 4]。第二轮排序结束，此时未排序部分的最大元素 4 也 “浮” 到了合适位置

…以此类推

可以发现每次都将最大的那个数送到最右边，假设有 n 个数，那么需要运送的趟数就为 (n-1)
每一轮，每两个数都要进行比较，已经被运送到最右边的就不需要比较
那么需要比较 (n-1-已经运送到右边的数的个数)

所以交换的函数可以这么写

void bubble_sort(int arr[], int sz)//参数接收数组元素个数
{int i = 0;for(i=0; i<sz-1; i++){int j = 0;for(j=0; j<sz-i-1; j++){if(arr[j] > arr[j+1]){int tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;}}}}int main()
{int arr[] = {3,1,7,5,8,9,0,2,4,6};int sz = sizeof(arr)/sizeof(arr[0]);bubble_sort(arr, sz);int i = 0;for(i=0; i<sz; i++){printf("%d ", arr[i]);}return 0;
}

这里简单说明一下时间复杂度的概念，这里只需要理解概念即可，如何计算到了C数据结构会讲解

1.时间复杂度是用来衡量算法运行时间随着输入规模增长而增长的趋势的一个重要指标
2. 时间复杂度通常用大 O 表示法来表示,大 O 表示法描述的是算法在最坏情况下的时间复杂度，也就是当输入对算法运行造成最大困难时的运行时间增长趋势

对于该冒泡排序
最坏情况：当输入的数组是完全逆序时，第一轮需要比较 n-1 次，第二轮需要比较 n-2 次，以此类推，总共需要比较的次数为 (n-1)+(n-2)+…+1，这个和等于 n (n-1)/2，所以需要进行 n(n-1)/2 次比较和交换操作，所以时间复杂度为 O(n^2)，其中 n 是数组的元素个数

最好情况：当输入的数组已经是有序的，只需要进行一轮比较（每个元素都和它相邻的元素比较一次），此时时间复杂度为 O(n)

假设有多个序列需要排列，所以为了提高效率，对最好情况进行快速排序，对代码可进行如下优化

void bubble_sort(int arr[], int sz)//参数接收数组元素个数
{int i = 0;for(i=0; i<sz-1; i++){int flag = 1;//假设这⼀趟已经有序了int j = 0;for(j=0; j<sz-i-1; j++){if(arr[j] > arr[j+1]){flag = 0;//发⽣交换就说明，⽆序int tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;}}if(falg == 1)//这⼀趟没交换就说明已经有序，后续⽆序排序了break;}}int main()
{int arr[] = {3,1,7,5,8,9,0,2,4,6};int sz = sizeof(arr)/sizeof(arr[0]);bubble_sort(arr, sz);int i = 0;for(i=0; i<sz; i++){printf("%d ", arr[i]);}return 0;
}

冒泡排序虽然简单易懂，但由于其时间复杂度较高，在处理大规模数据排序时效率相对较低，通常会被更高效的排序算法如快速排序、归并排序等所替代,但在一些数据量较小且对排序效率要求不是特别高的场景下，仍然可以使用冒泡排序

2.二分查找

二分查找（Binary Search），也叫折半查找，是一种用于在有序数组（或其他有序数据结构）中快速查找特定元素的高效查找算法

核心思想：不断对半查找

基本原理
1.每次查找时都将待查找的区间分成两部分
2.然后根据要查找元素与中间元素的比较结果，确定下一次查找应该在左半部分还是右半部分继续进行
3.如此反复，直到找到目标元素或者确定目标元素不存在为止

还是通过举例来说明，假设我们有一个有序数组 [1, 3, 5, 7, 9, 11, 13, 15]，要查找元素 7

首先，确定整个数组为待查找区间，计算中间元素的索引，对于长度为 n 的数组，中间元素索引 mid 计算公式为：mid = (left + right) / 2（这里 left 表示区间的左端点，right 表示区间的右端点，在初始时 left = 0，right = n - 1）。在这个例子中，n = 8，所以 mid = (0 + 7) / 2 = 3，中间元素就是 7

然后，将目标元素 7 与中间元素 7 进行比较，发现它们相等，这就找到了目标元素，查找过程结束

再假设要查找元素 4

1.同样先确定整个数组为待查找区间，计算中间元素索引 mid = (0 + 7) / 2 = 3，中间元素是 7
2.将目标元素 4 与中间元素 7 进行比较，因为 4 < 7，所以目标元素如果存在，一定在左半部分。此时更新待查找区间为左半部分，即 left = 0，right = mid - 1 = 2
3.再次计算新的中间元素索引 mid = (0 + 2) / 2 = 1，新的中间元素是 3
将目标元素 4 与新的中间元素 3 进行比较，因为 4 > 3，所以目标元素如果存在，一定在右半部分，更新待查找区间为右半部分，即 left = mid + 1 = 2，right = 2
4.第三次计算中间元素索引 mid = (2 + 2) / 2 = 2，中间元素是 5
5.将目标元素 4 与中间元素 5 进行比较，因为 4 < 5，所以目标元素如果存在，一定在左半部分，更新待查找区间为左半部分，即 left = 2，right = mid - 1 = 1，此时 left > right，说明目标元素在这个有序数组中不存在，查找过程结束

可以发现每次折中查找，然后和目标元素比较，以此往复完成二分查找

对于二分查找
二分查找每次查找都会将搜索范围缩小一半，最多需要查找的次数为以 2 为底，n（数组元素个数）的对数次
即 log 2^n ，所以二分查找的时间复杂度为 O(log n)，这使得它在处理较大规模的有序数组时，查找速度比顺序查找（时间复杂度为 O(n)）快得多

例如，当数组有 1024 个元素时，二分查找最多只需要查找 10 次（因为）就可以确定目标元素是否存在
如果是顺序查找就要找 1024 次，往往查找的数目还不止这么多，甚至更加庞大


int binary_search(int arr[], int n, int target)
{int left = 0;int right = n - 1;while (left <= right){// 计算中间元素的索引int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] > target) {right = mid - 1;} else{left = mid + 1;}}return -1;
}int main()
{int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};int n = sizeof(arr) / sizeof(arr[0]);int target = 7;int result = binary_search(arr, n, target);if (result!= -1) {printf("目标元素 %d 在数组中的索引为 %d\n", target, result);} else {printf("目标元素 %d 在数组中不存在\n", target);}return 0;
}

二分查找是一种非常高效的查找算法，但它的前提是数组必须是有序的。如果数组未排序，则需要先对数组进行排序，再使用二分查找

3.转移表

转移表是一种数据结构和编程技巧，用于实现根据不同的条件或输入值快速跳转到相应的代码段执行

例如：写一个简单的计算器程序，它可以执行加、减、乘、除四种运算。你可以创建一个转移表，表中包含四个元素，分别对应四种运算的处理函数的指针，当用户输入一个运算符号后，程序可以根据这个符号在转移表中快速找到对应的处理函数并执行，而不需要使用一长串的 if-else 或 switch 语句来逐个判断运算符号并调用相应函数

根据前面所学的 switch 结构和加法函数，可以写出一个简易的四则运算计算器

int add(int a, int b)
{return a + b;
}
int sub(int a, int b)
{return a - b;
}
int mul(int a, int b)
{return a * b;
}
int div(int a, int b)
{return a / b;
}int main()
{int x, y;int input = 1;int ret = 0;do{printf("*************************\n");printf("    1:add          2:sub \n");printf("    3:mul          4:div \n");printf("    0:exit               \n");printf("*************************\n");printf("请选择：");scanf("%d", &input);switch (input){case 1:printf("输⼊操作数：");scanf("%d %d", &x, &y);ret = add(x, y);printf("ret = %d\n", ret);break;case 2:printf("输⼊操作数：");scanf("%d %d", &x, &y);ret = sub(x, y);printf("ret = %d\n", ret);break;case 3:printf("输⼊操作数：");scanf("%d %d", &x, &y);ret = mul(x, y);printf("ret = %d\n", ret);break;case 4:printf("输⼊操作数：");scanf("%d %d", &x, &y);ret = div(x, y);printf("ret = %d\n", ret);break;case 0:printf("退出程序\n");break;default:printf("选择错误\n");break;}} while (input);return 0;
}

但是这种写法过于重复啰嗦，可以运用函数数组指针来简化代码

int add(int a, int b)
{return a + b;
}
int sub(int a, int b)
{return a - b;
}
int mul(int a, int b)
{return a * b;
}
int div(int a, int b)
{return a / b;
}int main()
{int x, y;int input = 1;int ret = 0;int(*p[5])(int x, int y) = {0, add, sub, mul, div };//转移表do{printf("*************************\n");printf("    1:add          2:sub \n");printf("    3:mul          4:div \n");printf("    0:exit               \n");printf("*************************\n");printf("请选择：");scanf("%d", &input);if ((input <= 4 && input >= 1)){printf( "输⼊操作数：" );scanf( "%d %d", &x, &y);ret = (*p[input])(x, y);printf( "ret = %d\n", ret);}else if(input == 0){printf("退出计算器\n");}else{printf( "输⼊有误\n" ); }}while (input);return 0;
}