快速排序算法：平均状况下排序 n 个项目要 Ο(nlogn)次比较

快速排序算法：平均状况下排序 n 个项目要 Ο(nlogn)次比较

算法一：快速排序算法

快速排序是托尼·霍尔（Tony Hall）开发的一种排序算法。平均而言，对 n 个项目进行排序需要 O(nlogn) 次比较。在最坏的情况下，需要进行 O(n2) 次比较，但这种情况并不常见。

事实上，快速排序通常比其他 Ο(nlogn) 算法快得多，因为它的内部循环（）可以在大多数架构上高效实现。

快速排序使用分治（-and-）策略将一个列表分成两个子列表。

算法步骤：

1. 从序列中选择一个元素，称为“枢轴”，

2. 重新排序序列，使所有小于基值的元素都放在基值前面，所有大于基值的元素放在基值后面（两边都可以放相同的数字）。

该分区退出后，碱基位于序列的中间。这称为() 操作。

3、递归地()对小于基值的元素子数组和大于基值的元素子数组进行排序。

递归的最底情况是当数组的大小为零或一时，即它一直是排序的。虽然递归继续进行，但是这个算法总是会退出，因为在每次迭代()中，它都会将至少一个元素移动到它的最终位置。

算法2：堆排序算法

堆排序（Heap Sort）是指利用堆的数据结构设计的排序算法。堆叠是一种近似完全二叉树的结构，满足堆叠的性质：即子节点的键值或索引总是小于（或大于）其父节点。

堆排序的平均时间复杂度为Ο(nlogn)。

算法步骤：

1.创建堆H[0..n-1]

2.交换堆头（最大值）和堆尾

3. 将堆大小减少 1 并调用 (0)。目的是将新数组的顶部数据调整到相应的位置。

4. 重复步骤2，直到堆大小为1

算法3：归并排序

归并排序（台译：merge sort）是一种基于归并操作的有效排序算法。该算法是分而治之法的一个非常典型的应用（）。

算法步骤：

1.申请空间，使其大小为两个已排序序列之和。该空间用于存储合并后的序列。

2.设置两个指针，初始位置为两个排序序列的起始位置。

3、比较两个指针所指向的元素，选择相对较小的元素放入合并空间，并将指针移动到下一个位置。

4. 重复步骤 3，直到指针到达序列末尾

5.将另一个序列的所有剩余元素直接复制到合并序列的末尾

算法4：二分查找算法

二分搜索算法是一种在有序数组中查找特定元素的搜索算法。

搜索过程从数组的中间元素开始。如果中间元素恰好是要查找的元素，则查找过程结束；如果特定元素大于或小于中间元素，则在数组中大于或小于中间元素的一半中搜索。 ，然后像开始一样从中间元素开始比较。

如果到了某个步骤数组为空，则说明找不到。该搜索算法每次比较都会将搜索范围缩小一半。半搜索每次将搜索区域缩小一半，时间复​​杂度为Ο(logn)。

算法5：BFPRT（线性搜索算法）

BFPRT算法解决的问题非常经典，就是从n个元素的序列中选择第k大（第k小）的元素。通过巧妙的分析，BFPRT可以保证在最坏情况下时间复杂度仍然是线性的。

这个算法的思想和快速排序类似。当然，为了让算法在最坏的情况下仍然达到o(n)的时间复杂度，五位算法作者做了精致的处理。

算法步骤：

1. 将 n 个元素分成 5 个组，并将它们分为 n/5（上限）组。

2. 取每组的中位数并使用任意排序方法，例如插入排序。

3、递归调用算法求上一步中所有中位数的中位数，将其设置为x，中位数为偶数的情况下，设置为选择中间较小的那个。

4、用x对数组进行划分，令小于等于x的数为k，大于x的数为nk。

5、如果i==k，则返回x；如果是ik，则递归地在大于x的元素中查找第ik个最小的元素。

终止条件：当n=1时，返回小元素i。

算法6：DFS（深度优先搜索）

深度优先搜索算法（Depth-First-）是搜索算法的一种。

它沿着树的深度遍历树的节点，搜索尽可能深的树的分支。当节点 v 的所有边都被探索完后，搜索将回溯到找到节点 v 的边的起始节点。

此过程持续进行，直到发现从源节点可到达的所有节点。如果还有未发现的节点，则选择其中一个作为源节点，重复上述过程。重复整个过程，直到访问完所有节点。 DFS是一种盲目搜索。

深度优先搜索是图论中的经典算法。可以利用深度优先搜索算法生成目标图对应的拓扑排序表。利用拓扑排序表可以方便地解决许多相关的图论问题，例如最大路径问题等。堆数据结构一般用来辅助实现DFS算法。

深度优先遍历图算法步骤：

1、访问顶点v；

2、从v的未访问过的相邻点开始，对图进行深度优先遍历，直到图中所有有路径连接到v的顶点都被访问过；

3、如果此时图中还有未访问的顶点，则从未访问的顶点开始，重复深度优先遍历，直到图中的所有顶点都被访问过。

上述描述可能比较抽象。这是一个例子：

访问图中的某个起始顶点v后，DFS从v开始，访问其任意相邻顶点w1；然后从w1开始，访问与w1相邻但尚未访问过的顶点w2；然后从w2开始进行类似的访问，...以这种方式进行，直到到达所有相邻顶点都被访问过的顶点u。

然后，退一步回到上次刚刚访问过的顶点，看看是否还有其他相邻的顶点没有访问过。

如果有，则访问这个顶点，然后从这个顶点出发，进行与上面类似的访问；如果没有，则返回一步进行搜索。重复上述过程，直到连通图中的所有顶点都被访问过。

算法7：BFS（广度优先搜索）

广度优先搜索算法（-First-）是一种图搜索算法。简单来说，BFS从根节点开始，沿着树（图）的宽度遍历树（图）的节点。

如果访问了所有节点，则算法中止。 BFS也是一种盲目搜索。队列数据结构一般用来辅助实现BFS算法。

算法步骤：

1.首先将根节点放入队列中。

2. 从队列中删除第一个节点并检查它是否是目标。如果找到目标，则搜索结束并返回结果。否则，将其所有尚未测试的直接子级添加到队列中。

3、如果队列为空，则说明整张图片都已检查完毕——即图片中没有要搜索的目标。结束搜索并返回“未找到目标”。

4. 重复步骤 2。

算法8：算法

算法（'）是由荷兰计算机科学家 提出的。

算法采用广度优先搜索来解决非负带权有向图的单源最短路径问题。算法最终得到一棵最短路径树。该算法通常用于路由算法或作为其他图算法的子模块。

算法的输入由带权有向图G和G中的源顶点S组成。设V表示G中所有顶点的集合。

图中的每条边都是由两个顶点形成的有序元素对。 (u,v)表示有一条从顶点u到v的路径。我们用E表示G中所有边的集合，边的权重由权重函数w:E→[0,∞定义]。因此，w(u,v)是从顶点u到顶点v的非负权重()。

边的权重可以被认为是两个顶点之间的距离。任意两点之间的路径的权重是该路径上所有边的权重之和。已知V中存在顶点s和t，算法可以找到从s到t的最低权重路径（例如最短路径）。

该算法还可以找到图中从顶点 s 到任何其他顶点的最短路径。对于无负权重的有向图，该算法是目前已知最快的单源最短路径算法。

算法步骤：

1、初始命令S={V0}，T={剩余顶点}，T中顶点对应的距离值，如果存在，则d(V0,Vi)为弧上的权重；如果不存在，则 d(V0,Vi ) 为 ∞。

2、选择距T距离值最小且不在S中的顶点W，将其添加到S中

3、修改T中剩余顶点的距离值：如果添加W作为中间顶点，V0到Vi的距离值缩短，则修改这个距离值

重复上面的步骤2和3，直到S包含所有顶点，即W=Vi

算法9：动态规划算法

动态规划（ ）是数学、计算机科学和经济学中使用的一种通过将原始问题分解为相对简单的子问题来解决复杂问题的方法。

动态规划通常适用于具有重叠子问题和最优子结构属性的问题。动态编程方法通常比朴素解决方案花费的时间少得多。

动态规划背后的基本思想非常简单。粗略地说，为了解决一个给定的问题，我们需要解决它的不同部分（即子问题），然后将子问题的解决方案组合起来得出原始问题的解决方案。

通常许多子问题非常相似，因此动态规划尝试只解决每个子问题一次，从而减少计算量：一旦计算出给定子问题的解决方案，就会将其记忆并存储，以备下次需要相同的子问题时使用求解时直接查表即可。当重复子问题的数量随着输入的大小呈指数增长时，这种方法特别有用。

动态规划最经典的问题无疑是背包问题。

算法步骤：

1. 最佳的下部结构特性。如果一个问题的最优解包含同样最优的子问题的解，我们就说该问题具有最优子结构性质（即满足优化原理）。

最优子结构性质为动态规划算法解决问题提供了重要线索。

2.子问题的重叠性。子问题的重叠性是指当使用递归算法从上到下解决问题时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。

动态规划算法利用了该子问题的重叠性质。它只对每个子问题计算一次，然后将其计算结果保存在表中。当需要再次计算已计算的子问题时，只在表中计算。只需查看结果即可获得高效率。

算法10：朴素贝叶斯分类算法

朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类的基础是概率推理，即在各种条件是否存在不确定、只知道其发生的概率的情况下，如何完成推理和决策任务。

概率推理与确定性推理相对应。朴素贝叶斯分类器基于独立性假设，即假设样本的每个特征与其他特征不相关。

朴素贝叶斯分类器依赖于准确的自然概率模型，可以在监督学习的样本集中取得非常好的分类结果。在许多实际应用中，朴素贝叶斯模型参数估计使用最大似然估计方法。换句话说，朴素贝叶斯模型可以在不使用贝叶斯概率或任何贝叶斯模型的情况下工作。

尽管有这些幼稚的想法和过于简化的假设，朴素贝叶斯分类器在许多复杂的现实情况中仍然可以取得相当好的结果。

（超过）