大数据工程师必备：详解数据分析中的经典算法

大数据工程师必备：详解数据分析中的经典算法

在大数据行业，懂算法的大数据工程师具有非常核心的竞争力。经过之前的面试，科大数据的一位实习生回来给我们分享，在面试过程中了解算法是一个很大的加分，即使算法底层逻辑不是很清楚，但是一定要了解具体的应用。本文详细讲解了数据分析中的几种经典算法，帮助大家更好的学习。

- 一杯

算法一：快速排序法

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

事实上，快速排序通常比其他 Ο(n log n) 算法快得多，因为它的内部循环可以在大多数架构上高效实现。快速排序使用分而治之（and）策略将列表分为两个子列表。

算法步骤

从序列中挑选出一个元素称为“枢轴”。

对数组重新排序，使所有小于基值的元素都放在基数前面，所有大于基值的元素放在基数后面（相同的数字可以到任意一侧）。该分区退出后，碱基位于序列的中间。这称为() 操作。

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

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

算法2：堆排序算法

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

算法步骤

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

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

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

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

算法3：归并排序

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

算法步骤

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

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

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

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

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

算法4：二分查找算法

二分搜索算法是一种在有序数组中查找特定元素的搜索算法。搜索过程从数组的中间元素开始。如果中间元素恰好是要查找的元素，则查找过程结束。

如果某个元素大于或小于中间元素，它将搜索数组中大于或小于中间元素的一半，并像以前一样从中间元素开始比较。如果到了某个步骤数组为空，则说明找不到。该搜索算法每次比较都会将搜索范围缩小一半。半搜索每次将搜索区域缩小一半，时间复​​杂度为Ο(logn)

算法 5：BFPRT（线性故障排除）

BFPRT算法解决的问题非常经典，就是从n个元素的序列中选择第k大（第k小）的元素。通过巧妙的分析，BFPRT可以保证在最坏情况下时间复杂度仍然是线性的。这个算法的思想和快速排序类似。当然，为了让算法在最坏的情况下仍然达到o(n)的时间复杂度，五位算法作者做了精致的处理。

算法步骤

将 n 个元素分为 5 个组，每个组分为 n/5（上限）组。

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

递归调用算法求上一步中所有中位数的中位数，将其设置为x。当中位数为偶数时，选择较小的那个。

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

如果i==k，则返回x；如果是ik，则递归地在大于x的元素中查找第ik个最小的元素。终止条件：当n=1时，返回第i个小元素。

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

深度优先搜索算法（Depth-First-）是搜索算法的一种。它沿着树的深度遍历树的节点，搜索尽可能深的树的分支。当节点 v 的所有边都被探索完后，搜索将回溯到找到节点 v 的边的起始节点。

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

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

算法步骤：

访问顶点v；

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

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

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

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

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

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

广度优先搜索算法（-First-）是一种图搜索算法。简单来说，BFS从根节点开始，沿着树（图）的宽度遍历树（图）的节点。如果访问了所有节点，则算法中止。 BFS也是一种盲目搜索。队列数据结构一般用来辅助实现BFS算法。

算法步骤

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

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

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

重复步骤 2。

算法八：

算法（'s'）是由荷兰计算机科学家 提出的。 算法采用广度优先搜索来解决非负带权有向图的单源最短路径问题。算法最终得到一棵最短路径树。该算法通常用于路由算法或作为其他图算法的子模块。

该算法的输入由带权有向图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 到任何其他顶点的最短路径。对于无负权重的有向图，该算法是目前已知最快的单源最短路径算法。

算法步骤

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

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

修改T中剩余顶点的距离值：如果添加W作为中间顶点，缩短V0到Vi的距离值，则修改这个距离值，重复上述步骤2和3，直到S包含所有顶点，即 W = Vi 直到