C语言中的算法

算法是为了解决一个问题或完成一项工作而按预定顺序执行的一系列指令。一个函数是一个代码块，可以从程序的其他部分调用和执行。

一组用于解决某个问题或进行某种活动的指令。在计算机科学中，算法被用于广泛的操作，从基本数学到复杂的数据处理。

C语言中常用的算法之一是排序算法。一个排序算法将一个项目集合按照一定的顺序排列，如按数字或字母顺序排列。

有许多排序算法，每种算法都有优点和缺点。C语言中最常见的排序算法是quicksort、merge和sort。

C语言的一个主要特点是支持指针。这允许对数据结构（如数组、队列等）进行有效操作。这使得它适合实现需要复杂数据操作的算法，如排序和算法搜索。

用C语言实现的软件库的一个著名例子是标准模板库（STL）。这个库为排序、搜索和操作数据结构等任务提供了各种各样的算法。

算法的特点

它定义了算法的几个重要特征，包括。

输入： 算法必须接收可以表示为数值或数据的输入。
输出： 算法应该产生一些输出。它可以是一个问题的结果，也可以是为解决问题而设计的解决方案。
明确性： 算法必须被精确定义，使用计算机或其他系统可以明确遵循的毫不含糊的指令。
有限性： 算法需要有限的步骤。这意味着在执行了一定数量的指令后，它应该被退出。
有效性： 该算法必须是有效的。换句话说，它应该能够在合理的时间内产生该算法所要解决的问题的解决方案。
有效性 ：一个算法必须是有效的，也就是说，它必须能够在合理的时间内产生它所要解决的问题的解决方案。
通用性： 一个算法必须是通用的，也就是说，它可以应用于广泛的问题，而不是专门针对一个问题。

算法分析

算法分析是在效率、复杂性和其他标准方面评估算法性能的过程。通常，这样做是为了评估许多算法，并为某个问题或某个软件选择最佳解决方案。

对算法的分析通常涉及测量其时间和空间复杂性。

与描述所需内存或磁盘空间数量的空间复杂度一样，时间复杂度描述了一个算法确定执行一项任务的时间。

有不同的方法来分析算法的时间复杂性，如大O和欧米茄符号。欧米茄符号为算法的时间复杂性提供了一个上限，而欧米茄符号则提供了一个下限。

除了测量时间和空间复杂度外，算法分析还包括其他标准，如稳定性、并行性和可扩展性。

稳定性 :- 这指的是算法保持数据集中元素的相对顺序的能力。
并行性 :- 这是指在几个处理器上并行执行操作的能力。
可扩展性 :- 另一方面，它指的是一个算法处理大量数据和其他输入的能力。

它们包括两种类型的分析。

它们是：-

先验分析。
后验分析。

先验分析

Prior是一种算法分析方法，主要是根据算法的数学特性来估计算法的性能，而不需要实际执行该算法。

这种方法允许你分析算法的时间和空间复杂性以及其他指标，而不需要实施和运行算法。

后验分析

另一方面，后验分析是一种算法分析的方法，它实际执行算法并测量其性能。

这种方法提供了关于算法性能的更准确和详细的信息，但需要实施和执行算法。

算法复杂度

算法复杂性是衡量算法效率和性能的一种措施。算法通常是以解决一个问题或实现一个特定目标所需的时间和空间来评估的。

在算法的复杂性中使用了两个因素。

它们是：-

时间因素。
空间因素。

时间因素

一个算法完成一项任务所需的时间被称为时间复杂性。它通常由一个算法为解决一个问题所必须执行的操作或步骤的数量来衡量。
一个算法的时间复杂度很重要，因为它决定了它需要多长时间来执行，并可能对程序和系统性能产生重大影响。
算法的时间复杂度可以用大O符号来表达，这是一种表达算法时间复杂度上限的方式。
一个时间复杂度为O(n)的算法意味着运行该算法所需的时间与输入数据的大小（n）成正比。
其他常见的时间复杂度是O(n^2)二次复杂性和O(log n)对数复杂性。

空间分析

另一方面，空间复杂度是指执行算法所需的内存或存储空间的数量。
这很重要，因为它决定了运行算法所需的资源数量，会影响你的应用程序或系统的整体性能。
如果算法的空间复杂度为O(n)，它使用的内存量就会随着输入的大小而线性增长。
如果算法的空间复杂度为O(1)，那么无论输入的大小如何，它都会使用一个固定的内存量。

如何写一个算法

1.首先定义你希望算法解决的问题。

例如，假设我们想写一个算法，从一串数字中找出最大值。

2. 2. 将问题分解成较小的、可管理的步骤。

将 “max “变量初始化为列表中的第一个值。
对于列表中的每个后续值，与 “max “比较。
如果该值大于 “max”，将 “max “设置为该值。
继续这样做，直到列表中的每个值都被比较过。
返回最终的 “max “值。

3.用伪代码或编程语言写出你的算法。

用伪代码写的算法。

MAX (list)
    max = list[0]
    For i = 1 the length of the list
        list IF[i] > max
            max = list[i]
    End for
    Maximum return
Maximum end

4.测试你的算法，确保它是正确和有效的。

你可以通过输入不同的数字列表来测试该算法，并验证它是否返回最大的正确值。你也可以分析你的算法的时间复杂度，以确定它对更大的输入有多大的扩展性。

例子：-

输入。[1, 5, 2, 7, 3]

输出。7.

解释。7是列表中的最大值。

5.优化算法。

寻找优化算法的方法，使其更快、更有效。这可能涉及修改伪代码或实现更有效的数据结构或算法。

算法的基本写法

例子： -两个整数的总和。

第1步 开始

第2步 声明三个整数a、b、c

第3步 定义a和b的值

第4 步 – 将a和b的值相加

第5 步–将第4步的输出保存在c中

第6步 打印c

第7步 停止

C语言中使用的算法类型。

1.排序算法

C语言提供了一套丰富的数据类型和运算符，可以用来实现各种排序算法，如冒泡排序、插入排序和快速排序。

这些算法在许多应用中都很有用，因为它们可以用来对不同大小和类型的数据进行排序。

有 不同的排序算法。

它们是：-

(i) 泡沫排序： 一种不复杂的排序算法，它反复比较附近的组件，如果它们不符合顺序，就把它们换掉。

泡沫排序的算法是：-

从一个未经排序的元素列表开始。
比较列表中的前两个元素。如果第一个元素比第二个元素大，就把它们换掉。
转移到下一对元素，重复第2步，直到到达列表的末端。
对于列表上的每一个项目，再重复一次步骤2和3。这被称为通过。
对整个列表重复第2-4步。当你重复传递时，元素将 “冒泡 “到它们在排序列表中的正确位置。
一旦完成了一个传递，并且没有进行交换，列表就被排序了，算法就可以停止。
最终排序后的列表会被返回。

(ii) 插入式排序： 一种排序方法，通过将每个元素放在适当的位置上，每次创建一个排序的列表。

插入排序的算法是：

初始化一个空的排序列表和一个待排序元素的未排序列表。
应从未排序的列表中取出第一个成员，并将其放在排序列表中的适当位置。
对未排序列表中的每个后续元素重复步骤2。
将当前元素与排序列表中的元素进行比较，从紧邻左边的元素开始。
如果当前的元素比它左边的元素小，就交换这两个元素。
如果当前元素比它左边的元素大，就在排序列表中的正确位置插入它。
对未排序列表中的每个后续元素重复步骤4-6。
一旦所有的元素都被处理完毕，排序后的列表将以正确的顺序包含所有元素。
排序过程就完成了。

( 选择排序： 一种排序方法，它始终从无序列表中最小的细节开始排序列表。

选择排序的算法是：

开始时，将列表中的主要元素设置为最小元素。
重复浏览列表中的其余项目，将每个项目与当前的最小值进行比较。
如果发现一个元素小于现有的最小值，就设置一个新的最小值。
只要达到结论，就将当前最小值改为列表中的第一个元素。
对于列表中剩余的未排序部分，重复步骤2-4，但从列表中的第二个项目开始（因为第一个元素已经排序了）。
继续以这种方式对列表进行排序，直到全部排序完毕。

(iv) 快速排序： 一种分而治之的排序算法，它选择一个枢轴元素，并根据元素是否少于或多于枢轴元素，将列表分成子列表。之后，这些子列表被反复排序，直到整个列表被排序完毕。

快速排序的算法是：-

从列表中选择一个支点元素。这通常是第一个元素，但它也可以是一个随机元素或列表的中位数。
将列表分成两个子列表：一个包含小于中枢的元素，一个包含大于中枢的元素。
使用同样的程序对包含小于枢轴的元素的子列表进行递归排序。
使用同样的程序对大于枢轴的条目的子列表进行递归排序。
将排序后的子列表与中间的枢轴元素连接起来，形成一个完全排序的列表。
返回完全排序后的列表。

(v) 合并排序： 分而治之的排序算法将列表分成两半，对每一半进行排序，然后将两半按排序顺序合并。

合并排序算法。

从列表中做出两个子列表：一个是元素在枢轴以下的，一个是元素在枢轴以上的。
通过迭代合并子列表产生一个新的排序子列表，直到只存在一个子列表。这将是你的排序列表。
合并两个子目录的步骤：-
创建一个空列表来保存排序后的元素。
比较每个子列表的第一个元素。
将较小的元素添加到新列表中，并将其从父子列表中删除。
重复步骤2和3，直到列表完全为空。
将其他子列表中的剩余元素添加到新的列表中。
将合并后的子列表替换为新的排序后的列表。
重复这个过程，直到所有的子列表都被合并成一个排序的列表。

(vi) Heapsort : 一种使用称为堆的数据结构对元素进行排序的排序算法。

这就是分类算法。

建立最大堆 : 从第一个非叶子节点开始，将每个节点与它的子节点进行比较，用它的子节点中最大的一个替换节点，以满足最大堆属性。
将根与最后一个元素交换： 将根（最大的元素）与堆中的最后一个元素交换。
将其余的元素堆叠起来。从根开始，每个节点与它的子节点进行比较，将节点与它们的较大的子节点进行交换，直到满足最大堆属性。
用新堆积的元素重复步骤2和3，除了最后一个元素在正确的位置。
重复这个过程，直到堆栈中只剩下一个元素。现在这就是排序了。
Heapify Down : 从根节点开始，它将元素与它的子节点进行比较，并与两者中较大的元素进行交换，直到满足最大堆属性。
Heapify Up : 从堆中的最后一个元素开始，将其与它的父元素进行比较，并与父元素交换，以满足最大堆属性。

(vii) 径向排序： 一种排序算法，根据元素的二进制表示的数字或位数对其进行排序。

径向排序的算法是：

确定输入列表的最大元素中包含多少个数字。
将一个变量，即数字位，初始化为1，它代表当前的数字位。
为每个可能的数字值（从0到9）创建一个空列表。
遍历输入列表，根据当前数字位置的值将每个元素添加到相应的列表中。
将所有的列表串联起来，按照数字列表的顺序形成新的列表。
digitPlace乘以10，移到下一个数字位。
对每个数字位重复第4-6步，直到最大的元素中的所有数字都被考虑。
最后的列表将按照元素的数字升序排序。
返回最终排序后的列表。

2.搜索算法

C语言还提供了必要的工具来实现各种搜索算法，如线性搜索和二进制搜索。这些算法可以快速找到数据集中的特定项目，使它们对广泛的应用非常有用。

有许多类型的搜索算法。

它们是：-

(i) 线性搜索： 一种基本的搜索算法，逐一检查列表中的每个项目，直到找到所需的项目。

线性搜索的算法：

定义算法的输入。线性搜索算法的输入是一个元素列表（或一个数组）和一个我们要搜索的目标元素。
将一个名为 “index “的变量初始化为-1。这个变量将被用来存储目标元素的索引，如果它被找到的话。
循环浏览元素列表。从第一个元素开始，逐一检查列表中的每个元素。
将目前的元素与所需的元素进行比较，进行评估。在索引变量中保留当前元素的索引，如果现代元素和目标元素相同则退出循环。
返回目标元素的索引。循环完成后，返回存储在索引变量中的值。如果没有找到目标元素，索引的值将是-1。

(ii) 二进制搜索： 一种搜索算法，其操作方式是将列表分成两半，在这两半中搜索，更有可能包括该元素。

二进制搜索的算法：

输入。一个有n个元素的排序列表和一个目标元素x。
初始化变量。将低指数设为0，高指数设为n-1，中指数设为（低+高）/2。
开始一个循环。当低指数小于或等于高指数时，重复以下步骤。
将中间元素与x比较。如果中间元素等于x，返回中间指数。
更新低索引或高索引。如果x大于中间元素，将低索引设置为中间+1。否则，将高索引设置为mid – 1。
更新中间索引。Mid = (low+high)/2。
循环结束。如果低指数大于高指数，那么x就不在列表中，算法返回失败。
输出。列表中x的索引或失败信息。

(iii) 深度优先搜索： 一种搜索算法，在转身之前尽可能地检查每个分支。

以下准则适用于深度优先搜索。

选择图形的起始顶点或节点来开始。
在第一个顶点上添加一个访问标记。
直接将起始顶点放入一个堆栈。
直到堆栈为空，重复以下操作。-

删除堆栈的顶点。
将弹出的顶点的每个未访问的邻居标记为访问并插入堆栈中。
1. 继续这个过程，直到图形中的所有顶点都被访问过。
2. 一旦所有顶点都被访问过，该算法就完成了，在图上进行深度优先搜索。

(iv) 广度优先搜索： 一种搜索算法，在移动到下一级之前探索一个节点的所有邻居。

广度优先搜索的算法是：

从根节点或初始状态开始。
将根节点添加到一个队列中。
检查队列是否为空；如果是，则终止该算法。
从队列中取出第一个元素并将其标记为已访问。
通过将其所有未访问的邻居加入队列来放大当代节点。
直到找到想要的节点或队列为空，重复步骤3到5。
如果找到目标节点，则返回从初步状态到目标状态的路径。
如果队列是空的，就终止这套规则，并报告说目标状态没有被识别。

(v) 插值搜索： 一种搜索算法，使用搜索到的元素的值来估计索引中的位置。

重要的是，阵列是均匀分布的。否则，它就是一种算法。

它的工作原理和预期的一样。

该算法可以总结为以下几点。

获得要搜索的输入列表和键值。
在列表的第一个和最后一个索引处初始化 Lower 和 upper 变量。
如果Lower值小于或等于High值，那么:-
1. 使用以下公式计算估计的位置：

pos = low + ((high – low) / (arr[high] – arr[low]))* (x – arr[low])。
1. 如果估计的位置值是一个关键值，则返回该位置。
2. c) 如果估计的位置值小于关键值，则将其设置为低值。
  
  Position + 1。
3. d) 如果估计的位置值大于键值设置值，位置-1向上。
如果没有找到键值，返回-1，表示该值不在列表中。

(vi) 跳跃搜索： 一种搜索方法，以恒定长度的步骤在列表上迭代，直到找到相关元素或确定它不再存在。

跳跃搜索算法如下。

首先，将跳转大小设置为数组元素数的平方根。
设置一个名为 “current “的变量为数组的第一个元素。
在数组上进行迭代，按跳跃大小进行跳跃，同时增加一个名为 “跳跃 “的变量。
如果现有的元素比所需的元素小，则进入下一个跳跃。
如果当前元素比目标元素大，在当前元素和前一个跳跃元素之间进行线性搜索，以找到目标元素。
如果在数组中没有找到目标元素，则返回-1，表示它不在数组中。
如果找到该元素，它将返回该元素在数组中的索引。

3.图形算法

C语言对指针和数据结构（如数组和链表）的支持使它适合于实现操作图的算法，如寻找图中两个节点之间的最短路径。

有不同类型的图形算法。

它们是：-

Dijkstra算法： 一种通过持续更新每个节点的最短距离来寻找图中两个节点之间最短路径的算法。
算法A*： 一种持续更新图中每个节点的最短路线的方法，以确定它们之间的最短路线。
Prim算法： 一种计算加权连接图最小生成树的方法。
Kruskal’s algorithm : 一种确定连接加权图的最低生成树的方法。
Bellman-Ford算法： 一种算法，即使在图有负边权重的情况下，也能显示特定供应节点和网络中每个其他节点之间的最短路径。

4.密码学算法

C语言支持低级别的操作和高效的数据操作，使其成为实现密码学中所用算法的理想选择，如数据加密和解密算法。

有不同类型的加密算法。

它们是：-

哈希算法： 这些算法从任意大小的输入产生固定大小的输出（哈希）。例子包括MD5、SHA-1和SHA-2。
对称密钥算法： 此类算法的加密和解密步骤采用相同的私人密钥。AES、DES和Blowfish是几个例子。
非对称密钥算法： 这些方法使用一个公共密钥和一个非公共密钥作为加密和解密的独立密钥。一些例子包括 RSA, ECC, 和 DSA。
密钥交换算法： 这些算法允许双方在一个不安全的渠道上安全地交换密钥。例如，我们可以提到 Diffie-Hellman 和 Elliptic Curve Diffie-Hellman。