根据当前所学C语言知识，对前面知识进行及时的总结巩固，出了这么一篇 vlog 介绍当前所学知识能遇到的常见算法，这些算法是在C数据结构初阶常用的一些算法，重要性不言而喻，本章将用简单易懂的语言带领读者深入理解
1.冒泡排序
核心思想：
理论知识介绍完，举个例子或许你就完全明白了
假设我们有一个数组 [5, 4, 3, 2, 1] 要进行升序排序：
…以此类推
可以发现每次都将最大的那个数送到最右边，假设有 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数据结构会讲解
对于该冒泡排序
最坏情况：当输入的数组是完全逆序时，第一轮需要比较 n-1 次，第二轮需要比较 n-2 次，以此类推，总共需要比较的次数为 (n-1)+(n-2)+…+1，这个和等于 n (n-1)/2，所以需要进行 次比较和交换操作，所以时间复杂度为 ，其中 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.二分查找
核心思想：
还是通过举例来说明，假设我们有一个有序数组 [1, 3, 5, 7, 9, 11, 13, 15]，
再假设要
可以发现每次折中查找，然后和目标元素比较，以此往复完成二分查找
对于二分查找
二分查找每次查找都会将搜索范围缩小一半，最多需要查找的次数为以 2 为底，n（数组元素个数）的对数次
即 ，所以二分查找的时间复杂度为 ，这使得它在处理较大规模的有序数组时，查找速度比顺序查找（时间复杂度为 O(n)）快得多
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.转移表
转移表是一种数据结构和编程技巧，用于实现根据不同的条件或输入值快速跳转到相应的代码段执行
根据前面所学的 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;
}
这样就通过函数指针数组实现了根据不同的索引值灵活调用不同函数的功能，这在很多需要根据条件或情况动态选择执行不同函数的场景中非常有用
如果还有不懂可以私信博主或回顾往期 vlog 查缺补漏