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

文章目录

  • 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;
}

这样就通过函数指针数组实现了根据不同的索引值灵活调用不同函数的功能,这在很多需要根据条件或情况动态选择执行不同函数的场景中非常有用

如果还有不懂可以私信博主或回顾往期 vlog 查缺补漏

主页传送门:DARLING Zero two♡ 的 blog

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力!

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/908105.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

我也谈AI

“随着人工智能技术的不断发展&#xff0c;我们已经看到了它在各行业带来的巨大变革。在医疗行业中&#xff0c;人工智能技术正在被应用于病例诊断、药物研发等方面&#xff0c;为医学研究和临床治疗提供了新的思路和方法&#xff1b;在企业中&#xff0c;人工智能技术可以通过…

Flutter 13 网络层框架架构设计,支持dio等框架。

在移动APP开发过程中&#xff0c;进行数据交互时&#xff0c;大多数情况下必须通过网络请求来实现。客户端与服务端常用的数据交互是通过HTTP请求完成。面对繁琐业务网络层&#xff0c;我们该如何通过网络层架构设计来有效解决这些问题&#xff0c;这便是网络层框架架构设计的初…

Spring Boot2.x教程:(十)从Field injection is not recommended谈谈依赖注入

从Field injection is not recommended谈谈依赖注入 1、问题引入2、依赖注入的三种方式2.1、字段注入&#xff08;Field Injection&#xff09;2.2、构造器注入&#xff08;Constructor Injection&#xff09;2.3、setter注入&#xff08;Setter Injection&#xff09; 3、为什…

Nginx的基础架构解析(下)

1. Nginx模块 1.1 Nginx中的模块化设计 Nginx 的内部结构是由核心部分和一系列的功能模块所组成。这样划分是为了使得每个模块的功能相对简单&#xff0c;便于开发&#xff0c;同时也便于对系统进行功能扩展。Nginx 将各功能模块组织成一条链&#xff0c;当有请求到达的时候&…

【网络】网络层协议IP

目录 IP协议报头 报头分离和向上交付 四位版本 8位服务类型 16位总长度 八位生存时间 16位标识一行 网段划分 DHCP 私有IP范围 公网划分之CIDR 特殊的IP地址 缓解IP地址不够用的方法 NAT技术 路由 IP是用来主机定位和路由选择的&#xff0c;它提供了一种能力&am…

HTML 基础标签——多媒体标签<img>、<object> 与 <embed>

文章目录 1. `<img>` 标签主要属性示例注意事项2. `<object>` 标签概述主要属性示例注意事项3. `<embed>` 标签概述主要属性示例注意事项小结在现代网页设计中,多媒体内容的使用变得越来越重要,因为它能够有效增强用户体验、吸引注意力并传达信息。HTML 提…

【Canal 中间件】Canal 实现 MySQL 增量数据的异步缓存更新

文章目录 一、安装 MySQL1.1 启动 mysql 服务器1.2 开启 Binlog 写入功能1.2.1创建 binlog 配置文件1.2.2 修改配置文件权限1.2.3 挂载配置文件1.2.4 检测 binlog 配置是否成功 1.3 创建账户并授权 二、安装 RocketMQ2.1 创建容器共享网络2.2 启动 NameServer2.3 启动 Broker2.…

深度学习(九):推荐系统的新引擎(9/10)

一、深度学习与推荐系统的融合 深度学习在推荐系统中的融合并非偶然。随着互联网的飞速发展&#xff0c;数据量呈爆炸式增长&#xff0c;传统推荐系统面临着诸多挑战。例如&#xff0c;在处理大规模、高维度的数据时&#xff0c;传统方法往往显得力不从心。而深度学习以其强大的…

masm汇编字符串输出演示

assume cs:code, ds:datadata segmentmassage db zhouzunjie, 0dh, 0ah, $ data endscode segmentstart:mov ax, datamov ds, axmov ah, 09hlea dx, massageint 21hmov ax, 4c00hint 21hcode ends end start 效果演示&#xff1a;

在昇腾Ascend 910B上运行Qwen2.5推理

目前在国产 AI 芯片&#xff0c;例如昇腾 NPU 上运行大模型是一项广泛且迫切的需求&#xff0c;然而当前的生态还远未成熟。从底层芯片的算力性能、计算架构的算子优化&#xff0c;到上层推理框架对各种模型的支持及推理加速&#xff0c;仍有很多需要完善的地方。 今天带来一篇…

HarmonyOS一次开发多端部署三巨头之界面级一多开发

界面级一多开发 引言1. 布局能力1.1 自适应布局1.1.1 拉伸能力1.1.2 均分能力1.1.3 占比能力1.1.4 缩放能力1.1.5延伸能力1.1.6 隐藏能力1.1.7 折行能力 1.2 响应式布局1.2.1 断点和媒体查询1.2.2 栅格布局 2. 视觉风格2.1 分层参数2.2 自定义资源 3. 交互归一4. IDE多设备预览…

(58)LMS自适应滤波算法与系统辨识的MATLAB仿真

文章目录 前言一、LMS算法的基本步骤二、LMS算法的一些主要应用1. 通信系统2. 信号分离与增强3. 控制系统4. 生物医学信号处理5. 机器学习与模式识别6. 其他应用 三、LMS算法用于系统辨识的MATLAB仿真四、仿真结果 前言 LMS&#xff08;Least Mean Squares&#xff0c;最小均方…

bootstrap应用1——计算n从1-100000的每个整数,第j个观测在自助法样本里的概率。

计算n从1-100000的每个整数&#xff0c;第j个观测在自助法样本里的概率。 pr function(n) return(1 - (1 - 1/n)^n) x 1:10000 plot(x, pr(x))

AI-基本概念-向量、矩阵、张量

1 需求 需求&#xff1a;Tensor、NumPy 区别 需求&#xff1a;向量、矩阵、张量 区别 2 接口 3 示例 4 参考资料 【PyTorch】PyTorch基础知识——张量_pytorch张量-CSDN博客

【设计模式】策略模式定义及其实现代码示例

文章目录 一、策略模式1.1 策略模式的定义1.2 策略模式的参与者1.3 策略模式的优点1.4 策略模式的缺点1.5 策略模式的使用场景 二、策略模式简单实现2.1 案例描述2.2 实现代码 三、策略模式的代码优化3.1 优化思路3.2 抽象策略接口3.3 上下文3.4 具体策略实现类3.5 测试 参考资…

2025年PMP考试的3A好考吗?

确实&#xff0c;PMP正式抛弃第六版用第七版教材了&#xff0c;但是考纲还是跟24年一样的&#xff0c;情景题多&#xff0c;考的比之前灵活&#xff0c;但是 3A 的人也不少&#xff0c;按照机构的计划来学习并没有很难&#xff0c;给大家说说我的备考经历吧&#xff0c;希望对你…

VScode + PlatformIO 了解

​Visual Studio Code Visual Studio Code&#xff08;简称 VS Code&#xff09;是一款由微软开发且跨平台的免费源代码编辑器。该软件以扩展的方式支持语法高亮、代码自动补全&#xff08;又称 IntelliSense&#xff09;、代码重构功能&#xff0c;并且内置了工具和 Git 版本…

完美日记营销模式对开源 AI 智能名片 2 + 1 链动模式 S2B2C 商城小程序的启示

摘要&#xff1a;本文通过分析完美日记在营销中利用社会基础设施升级红利、网红与新流量平台、KOL 和私域流量等策略取得成功的案例&#xff0c;探讨其对开源 AI 智能名片 2 1 链动模式 S2B2C 商城小程序在营销推广、用户获取与留存、提升复购率等方面的启示&#xff0c;为商城…

Failed to install Visual Studio Code update

当关闭vsCode的时候&#xff0c;出现了下面的报错&#xff1a; 可能是之前将vscode文件换了位置导致的&#xff0c;并且vscode在桌面的图标也变成了下面这个&#xff1a; 解决方法&#xff1a; 找到上图路径的log文件并打开&#xff1a; 搜索电脑中的Code.exe文件 并粘贴到上…

python在word的页脚插入页码

1、插入简易页码 import win32com.client as win32 from win32com.client import constants import osdoc_app win32.gencache.EnsureDispatch(Word.Application)#打开word应用程序 doc_app.Visible Truedoc doc_app.Documents.Add() footer doc.Sections(1).Footers(cons…