每个程序员都应该知道的 40 个算法（一）（2）https://developer.aliyun.com/article/1506325
使用栈和队列的基本思想
让我们用一个类比来了解使用栈和队列的基本思想。假设我们有一张桌子，我们把我们从邮政服务收到的信放在上面，例如，加拿大邮件。我们堆积起来，直到有时间逐一打开和查看信件。有两种可能的做法：
- 我们把信放在一个栈里，每当我们收到一封新信时，我们把它放在栈的顶部。当我们想读一封信时，我们从顶部开始。这就是我们所说的 栈。请注意，最新的信件将位于顶部，并且将首先被处理。从列表顶部取出一封信称为 弹出 操作。每当有新信到达时，把它放在顶部称为 推入 操作。如果我们最终有一个相当大的栈，并且有大量信件不断到达，有可能我们永远没有机会到达等待我们的非常重要的信件。
- 我们把信放在一堆里，但我们想先处理最老的信：每次我们想看一个或多个信时，我们要确保先处理最老的那个。这就是我们所说的 队列。把一封信放到一堆里叫做 入队 操作。从一堆里取出一封信叫做 出队 操作。
树
在算法的上下文中，树是最有用的数据结构之一，因为它具有分层数据存储能力。在设计算法时，我们使用树来表示我们需要存储或处理的数据元素之间的分层关系。
让我们更深入地了解这个有趣且非常重要的数据结构。
每棵树都有一个有限的节点集，因此它有一个称为 根 的起始数据元素和一组由链接连接在一起的称为 分支 的节点。
术语
让我们来看一些与树数据结构相关的术语：
| 根节点 | 没有父节点的节点称为 根 节点。例如，在下图中，根节点是 A。在算法中，通常根节点保存树结构中最重要的值。 |
| 节点的级别 | 从根节点到节点的距离就是节点的级别。例如，在下图中，节点D，E和F的级别为 2。 |
| 兄弟节点 | 树中的两个节点如果在同一级别，则称为兄弟节点。例如，如果查看下图，节点B和C是兄弟节点。 |
| 子节点和父节点 | 如果节点C和节点F直接连接，并且节点C的级别低于节点F，那么节点F是节点C的子节点。反之，节点C是节点F的父节点。下图中的节点C和F展示了这种父子关系。 |
| 节点的度 | 节点的度是它拥有的子节点数量。例如，在下图中，节点B的度为 2。 |
| 树的度 | 树的度等于树的组成节点中可以找到的最大度。例如，下图中呈现的树的度为 2。 |
| 子树 | 树的子树是树的一部分，选择的节点是子树的根节点，所有子节点是树的节点。例如，在下图中呈现的树的节点E的子树包括节点E作为根节点和节点G和H作为两个子节点。 |
| 叶节点 | 树中没有子节点的节点称为叶节点。例如，在下图中，D，G，H和F是四个叶节点。 |
| 内部节点 | 既不是根节点也不是叶节点的任何节点都是内部节点。内部节点至少有一个父节点和至少一个子节点。 |
请注意，树是我们将在第六章中学习的网络或图的一种，无监督机器学习算法。对于图和网络分析，我们使用术语链接或边而不是分支。大多数其他术语保持不变。
树的类型
树有不同的类型，如下所述：
- 二叉树： 如果一棵树的度为 2，则称该树为二叉树。例如，下图中呈现的树是一棵二叉树，因为它的度为 2：
请注意，前图显示了一个有四个级别和八个节点的树。
- 满树： 所有节点的度都相同的树称为满树，其度将等于树的度。下图展示了前面讨论过的树的类型：
请注意，左侧的二叉树不是一棵满树，因为节点C的度为 1，而所有其他节点的度为 2。中间的树和左侧的树都是满树。
- 完美树： 完美树是一种特殊类型的满树，其中所有叶节点都在同一级别。例如，右侧的二叉树如前图所示是一棵完美的满树，因为所有叶节点都在同一级别，即级别 2。
- 有序树： 如果节点的子节点根据特定标准有序排列，那么树被称为有序树。例如，树可以按照从左到右的升序顺序进行排序，同一级别的节点在从左到右遍历时值会增加。
实际例子
树是一种主要的数据结构之一，在开发决策树中被使用，将在第七章 传统监督学习算法中讨论。由于其分层结构，它在与网络分析相关的算法中也很受欢迎，将在第六章 无监督机器学习算法中详细讨论。树还被用于各种搜索和排序算法，其中需要实现分而治之的策略。
摘要
在本章中，我们讨论了可以用来实现各种类型算法的数据结构。通过阅读本章，我期望你能够选择合适的数据结构来存储和处理算法的数据。你还应该能够理解我们选择对算法性能的影响。
下一章是关于排序和搜索算法，我们将在算法的实现中使用本章介绍的一些数据结构。
第三章：排序和搜索算法
在本章中，我们将看一下用于排序和搜索的算法。这是一类重要的算法，可以单独使用，也可以成为更复杂算法的基础（在本书的后面章节中介绍）。本章首先介绍了不同类型的排序算法。它比较了各种设计排序算法的方法的性能。然后，详细介绍了一些搜索算法。最后，探讨了本章介绍的排序和搜索算法的一个实际例子。
在本章结束时，您将能够理解用于排序和搜索的各种算法，并能够理解它们的优势和劣势。由于搜索和排序算法是大多数更复杂算法的基础，详细了解它们将有助于您理解现代复杂算法。
以下是本章讨论的主要概念：
- 介绍排序算法
- 介绍搜索算法
- 一个实际的例子
让我们首先看一些排序算法。
介绍排序算法
在大数据时代，能够高效地对复杂数据结构中的项目进行排序和搜索是非常重要的，因为许多现代算法都需要这样做。正确的排序和搜索数据的策略将取决于数据的大小和类型，正如本章所讨论的。虽然最终结果是完全相同的，但对于实际问题的高效解决方案，需要正确的排序和搜索算法。
本章介绍了以下排序算法：
- 冒泡排序
- 归并排序
- 插入排序
- 希尔排序
- 选择排序
在 Python 中交换变量
在实现排序和搜索算法时，我们需要交换两个变量的值。在 Python 中，有一种简单的交换两个变量的方式，如下所示：
var1 = 1 var2 = 2 var1,var2 = var2,var1 >>> print (var1,var2) >>> 2 1
让我们看看它是如何工作的：
在本章中，这种简单的交换值的方式在排序和搜索算法中被广泛使用。
让我们从下一节开始看冒泡排序算法。
冒泡排序
冒泡排序是用于排序的最简单和最慢的算法。它被设计成这样，列表中的最高值会在算法循环迭代时冒泡到顶部。正如之前讨论的，它的最坏情况性能是 O(N²)，因此应该用于较小的数据集。
理解冒泡排序背后的逻辑
冒泡排序基于各种迭代，称为通行。对于大小为N的列表，冒泡排序将有N-1 个通行。让我们专注于第一次迭代：第一遍。
第一遍的目标是将最高的值推到列表的顶部。随着第一遍的进行，我们会看到列表中最高的值冒泡到顶部。
冒泡排序比较相邻的邻居值。如果较高位置的值比较低索引处的值要大，我们交换这些值。这种迭代会一直持续，直到我们到达列表的末尾。如下图所示：
现在让我们看看如何使用 Python 实现冒泡排序：
#Pass 1 of Bubble Sort lastElementIndex = len(list)-1 print(0,list) for idx in range(lastElementIndex): if list[idx]>list[idx+1]: list[idx],list[idx+1]=list[idx+1],list[idx] print(idx+1,list)
如果我们在 Python 中实现冒泡排序的第一遍，它将如下所示：
第一遍完成后，最高的值在列表的顶部。算法接下来进行第二遍。第二遍的目标是将第二高的值移动到列表中第二高的位置。为了做到这一点，算法将再次比较相邻的邻居值，如果它们不按顺序，则交换它们。第二遍将排除顶部元素，它已经被第一遍放在正确的位置上，不需要再次触摸。
完成第二次通行证后，算法将继续执行第三次通行证，直到列表的所有数据点按升序排列。算法将需要N-1 次通行证来完全对大小为N的列表进行排序。Python 中冒泡排序的完整实现如下：
现在让我们来看一下BubbleSort算法的性能。
冒泡排序的性能分析
很容易看出，冒泡排序涉及两个级别的循环：
- 外部循环：这也被称为通行证。例如，通行证一是外部循环的第一次迭代。
- 内部循环：这是当列表中剩余的未排序元素被排序时，直到最大值被冒泡到右侧。第一次通行证将有N-1 次比较，第二次通行证将有N-2 次比较，每次后续通行证将减少一次比较。
由于两个级别的循环，最坏情况下的运行时复杂度将是 O(n²)。
插入排序
插入排序的基本思想是，在每次迭代中，我们从数据结构中移除一个数据点，然后将其插入到正确的位置。这就是为什么我们称之为插入排序算法。在第一次迭代中，我们选择两个数据点并对它们进行排序。然后，我们扩展我们的选择并选择第三个数据点，并根据其值找到其正确的位置。算法进行到所有数据点都移动到它们的正确位置。这个过程如下图所示：
插入排序算法可以在 Python 中编写如下：
def InsertionSort(list): for i in range(1, len(list)): j = i-1 element_next = list[i] while (list[j] > element_next) and (j >= 0): list[j+1] = list[j] j=j-1 list[j+1] = element_next return list
请注意，在主循环中，我们遍历整个列表。在每次迭代中，两个相邻的元素分别是list[j]（当前元素）和list[i]（下一个元素）。
在list[j] > element_next和j >= 0中，我们将当前元素与下一个元素进行比较。
让我们使用这段代码来对数组进行排序：
让我们来看一下插入排序算法的性能。
从算法描述中很明显，如果数据结构已经排序，插入排序将执行得非常快。实际上，如果数据结构已排序，那么插入排序将具有线性运行时间；即 O(n)。最坏情况是每个内部循环都必须移动列表中的所有元素。如果内部循环由i定义，插入排序算法的最坏情况性能如下所示：
总通行证数量如下图所示：
一般来说，插入可以用于小型数据结构。对于较大的数据结构，由于二次平均性能，不建议使用插入排序。
归并排序
到目前为止，我们已经介绍了两种排序算法：冒泡排序和插入排序。如果数据部分排序，它们的性能都会更好。本章介绍的第三种算法是归并排序算法，它是由约翰·冯·诺伊曼于 1940 年开发的。该算法的特点是其性能不依赖于输入数据是否排序。与 MapReduce 和其他大数据算法一样，它基于分而治之的策略。在第一阶段，称为拆分，算法继续递归地将数据分成两部分，直到数据的大小小于定义的阈值。在第二阶段，称为合并，算法继续合并和处理，直到我们得到最终结果。该算法的逻辑如下图所示：
让我们首先看一下归并排序算法的伪代码：
mergeSort(list, start, end) if(start < end) midPoint = (end - start) / 2 + start mergeSort(list, start, midPoint) mergeSort(list, midPoint + 1, start) merge(list, start, midPoint, end)
正如我们所看到的算法有以下三个步骤：
- 它将输入列表分成两个相等的部分
- 它使用递归分割，直到每个列表的长度为 1
- 然后，它将排序好的部分合并成一个排序好的列表并返回它
实现MergeSort的代码如下所示：
当运行上述 Python 代码时，它会生成以下输出：
请注意，代码的结果是一个排序好的列表。
谢尔排序
冒泡排序算法比较相邻的元素，如果它们的顺序不正确，则交换它们。如果我们有一个部分排序的列表，冒泡排序应该会有合理的性能，因为它会在循环中不再发生元素交换时立即退出。
但对于完全无序的大小为N的列表，你可以说冒泡排序将不得不完全迭代N-1 次才能完全排序它。
唐纳德·谢尔提出了谢尔排序（以他的名字命名），质疑了选择相邻元素进行比较和交换的重要性。
现在，让我们理解这个概念。
在第一次通过中，我们不是选择相邻的元素，而是使用固定间隔的元素，最终对由一对数据点组成的子列表进行排序。如下图所示。在第二次通过中，它对包含四个数据点的子列表进行排序（见下图）。在后续的通过中，每个子列表中的数据点数量不断增加，子列表的数量不断减少，直到我们达到只有一个包含所有数据点的子列表的情况。此时，我们可以假设列表已排序：
在 Python 中，实现谢尔排序算法的代码如下所示：
def ShellSort(list): distance = len(list) // 2 while distance > 0: for i in range(distance, len(list)): temp = input_list[i] j = i # Sort the sub list for this distance while j >= distance and list[j - distance] > temp: list[j] = list[j - distance] j = j-distance list[j] = temp # Reduce the distance for the next element distance = distance//2 return list
上述代码可以用于对列表进行排序，如下所示：
请注意，调用ShellSort函数已导致对输入数组进行排序。
谢尔排序的性能分析
谢尔排序不适用于大数据。它用于中等大小的数据集。粗略地说，它在具有多达 6000 个元素的列表上具有相当不错的性能。如果数据部分处于正确的顺序，性能会更好。在最佳情况下，如果列表已经排序，它只需要通过N个元素进行一次验证，产生*O(N)*的最佳性能。
选择排序
正如我们在本章前面看到的，冒泡排序是最简单的排序算法之一。选择排序是对冒泡排序的改进，我们试图最小化算法所需的总交换次数。它旨在使每次通过只进行一次交换，而不是冒泡排序算法的N-1 次通过。我们不是像冒泡排序中那样逐步将最大值向顶部冒泡（导致N-1 次交换），而是在每次通过中寻找最大值并将其向顶部移动。因此，在第一次通过后，最大值将位于顶部。第二次通过后，第二大的值将位于顶部值旁边。随着算法的进行，后续的值将根据它们的值移动到它们的正确位置。最后一个值将在第(N-1)次通过后移动。因此，选择排序需要N-1 次通过来排序N个项目：
Python 中选择排序的实现如下所示：
def SelectionSort(list): for fill_slot in range(len(list) - 1, 0, -1): max_index = 0 for location in range(1, fill_slot + 1): if list[location] > list[max_index]: max_index = location list[fill_slot],list[max_index] = list[max_index],list[fill_slot]
当选择排序算法被执行时，它将产生以下输出：
请注意，最终输出是排序好的列表。
选择排序算法的性能
选择排序的最坏情况性能是O(N**²)。注意，它的最坏性能类似于冒泡排序，不应该用于对更大的数据集进行排序。尽管如此，选择排序比冒泡排序更好设计，并且由于交换次数的减少，其平均性能比冒泡排序更好。
选择排序算法
选择正确的排序算法取决于当前输入数据的大小和状态。对于已排序的小输入列表，使用高级算法会在代码中引入不必要的复杂性，而性能改善微乎其微。例如，对于较小的数据集，我们不需要使用归并排序。冒泡排序会更容易理解和实现。如果数据部分排序，我们可以利用插入排序。对于较大的数据集，归并排序算法是最好的选择。
搜索算法简介
在复杂数据结构中高效地搜索数据是最重要的功能之一。最简单的方法是在每个数据点中搜索所需的数据，但随着数据规模的增大，我们需要更复杂的为搜索数据设计的算法。
本节介绍了以下搜索算法：
- 线性搜索
- 二分搜索
- 插值搜索
让我们更详细地看看它们每一个。
线性搜索
搜索数据的最简单策略之一是简单地循环遍历每个元素寻找目标。每个数据点都被搜索匹配，当找到匹配时，结果被返回并且算法退出循环。否则，算法会继续搜索直到达到数据的末尾。线性搜索的明显缺点是由于固有的穷举搜索，它非常慢。优点是数据不需要像本章介绍的其他算法那样需要排序。
让我们来看一下线性搜索的代码：
def LinearSearch(list, item): index = 0 found = False # Match the value with each data element while index < len(list) and found is False: if list[index] == item: found = True else: index = index + 1 return found
现在让我们来看一下前面代码的输出：
注意，运行LinearSearch函数会在成功找到数据时返回True值。
线性搜索的性能
正如讨论的那样，线性搜索是一种执行穷举搜索的简单算法。它的最坏情况行为是O(N)。
二分搜索
二分搜索算法的先决条件是排序数据。该算法迭代地将列表分成两部分，并跟踪最低和最高索引，直到找到所寻找的值：
def BinarySearch(list, item): first = 0 last = len(list)-1 found = False while first<=last and not found: midpoint = (first + last)//2 if list[midpoint] == item: found = True else: if item < list[midpoint]: last = midpoint-1 else: first = midpoint+1 return found
输出如下：
注意，调用BinarySearch函数将在输入列表中找到值时返回True。
二分搜索的性能
二分搜索之所以被这样命名，是因为在每次迭代中，算法将数据分成两部分。如果数据有N个项目，迭代最多需要 O(logN)步。这意味着算法具有*O(logN)*的运行时间。
插值搜索
二分搜索基于将重点放在数据的中间部分的逻辑。插值搜索更加复杂。它使用目标值来估计已排序数组中元素的位置。让我们通过一个例子来理解它。假设我们想在英语词典中搜索一个单词，比如river。我们将利用这些信息进行插值，并开始搜索以r开头的单词。更一般化的插值搜索可以编程如下：
def IntPolsearch(list,x ): idx0 = 0 idxn = (len(list) - 1) found = False while idx0 <= idxn and x >= list[idx0] and x <= list[idxn]: # Find the mid point mid = idx0 +int(((float(idxn - idx0)/( list[idxn] - list[idx0])) * ( x - list[idx0]))) # Compare the value at mid point with search value if list[mid] == x: found = True return found if list[mid] < x: idx0 = mid + 1 return found
输出如下：
注意，在使用IntPolsearch之前，数组首先需要使用排序算法进行排序。
每个程序员都应该知道的 40 个算法（一）（4）https://developer.aliyun.com/article/1506327
