每个程序员都应该知道的 40 个算法（一）（3）-阿里云开发者社区

每个程序员都应该知道的 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