下载掌阅APP，畅读海量书库
立即打开
在这一章中，我们将学习用于排序和搜索的算法。这是一类重要的算法，可以单独使用，也可以成为更复杂算法的基础。这些算法包括自然语言处理和模式提取算法。本章首先介绍不同类型的排序算法，在此比较了设计排序算法的各种方法的性能。然后，详细介绍一些搜索算法。最后，将研究本章中介绍的排序和搜索算法的一个实际示例。
通过本章学习，你将能够了解用于排序和搜索的各种算法，并且可以了解它们各自的优势和劣势。由于搜索和排序算法是大多数更复杂算法的基础，因此详细了解它们也有助于你理解后面章节所述的现代复杂算法。
本章涵盖以下主题：
❑ 排序算法简介。
❑ 搜索算法简介。
❑ 排序和搜索算法的性能分析。
❑ 实际应用。
我们先来看一些排序算法。
有效地对复杂数据结构中的各数据项进行排序和搜索的能力非常重要，因为许多现代算法都需要这样的操作。如本章所述，在为数据恰当选择排序和搜索策略时，需要根据数据的规模和类型进行判断。虽然最终结果是相同的，但为了有效解决现实世界的问题，需要选择正确的排序和搜索算法。因此，仔细分析这些算法的性能是很重要的。
排序算法在分布式数据存储系统中被广泛应用，比如现代的NoSQL数据库，它们支持集群和云计算架构。在这种数据存储系统中，数据元素需要定期进行排序和存储，以便能够高效地检索数据。
本章中介绍了以下排序算法：
❑ 冒泡排序（Bubble Sort）
❑ 插入排序（Insertion Sort）
❑ 归并排序（Merge Sort）
❑ 希尔排序（Shell Sort）
❑ 选择排序（Selection Sort）
在研究这些算法之前我们首先需要讨论一下将要在本章代码中使用的Python中的变量交换技术。
在实现排序和搜索算法时，需要交换两个变量的值。在Python中，有一种标准的方法来交换两个变量的值，示例如下：
本章的所有排序和搜索算法中都使用了这种简单的方法来交换变量值。
下面，我们从冒泡排序开始学习。
冒泡排序是一种最简单但速度较慢的排序算法之一。它的设计思想是通过迭代循环，使数据列表中的最大值逐渐“冒泡”到列表的顶部。冒泡排序需要较少的运行时内存，因为所有排序操作都在原始数据结构内部进行，不需要额外的临时缓冲区。但是，它在最坏情况下的性能是 O ( N 2 )，即二次时间复杂度（其中 N 是待排序元素的数量）。正如下文所述，建议仅在较小的数据集上使用冒泡排序。对于使用冒泡排序进行排序的数据规模的实际推荐限制将取决于可用的内存和处理资源，但通常推荐保持元素数量（ N ）在1000以下。
理解冒泡排序背后的逻辑
冒泡排序基于各种迭代（称为遍历）。对于大小为 N 的列表，冒泡排序将会进行 N -1轮遍历。为了理解其工作原理，我们着重讨论第一次迭代，也就是第一次遍历。
第一次遍历的目标是将最大值推到最高索引（列表顶部）。换句话说，随着第一次遍历的进行，我们会看到列表中最大的值逐渐“冒泡”到顶部。
冒泡排序的逻辑是基于比较相邻的元素值。如果较高索引处的值大于较低索引处的值，则交换这两个值。这种迭代会持续直到达到列表末尾。这在图3.1中有所展示。
图3.1 冒泡排序算法
现在让我们看一下如何使用Python实现冒泡排序。如果我们在Python中实现冒泡排序的第一次遍历，代码如下所示：
请注意，在第一次遍历之后：
❑ 最大值位于列表顶部，存储在索引idx+1处。
❑ 在执行第一次遍历时，算法必须逐个比较列表的每个元素，以将最大值“冒泡”到顶部。
在完成第一次遍历后，算法将继续进行第二次遍历。第二次遍历的目标是将第二大的值移动到列表的第二大索引处。为了实现这一点，算法将再次比较相邻的元素值，如果它们的顺序不对则交换它们。第二次遍历将排除顶部索引处的值，该值已经由第一次遍历放置在正确的位置上。因此，它处理的数据元素将少一个。
在完成第二次遍历后，算法将继续执行第三次遍历以及后续的遍历，直到列表中的所有数据点按升序排列。对于大小为 N 的列表，算法将需要 N -1次遍历才能完全对其进行排序。
我们提到的性能是冒泡排序算法的一个限制因素。让我们通过冒泡排序算法的性能分析来量化冒泡排序的性能：
优化冒泡排序
上面使用bubble_sort函数实现的冒泡排序是一种直接的排序方法，其中不断比较相邻元素并在它们的顺序不正确时进行交换。在最坏情况下，该算法始终需要 O ( N 2 )次比较和交换，其中 N 是列表中的元素数量。这是因为对于一个包含 N 个元素的列表，该算法无论列表的初始顺序如何都会经过 N -1次遍历。
下面是优化后的冒泡排序版本：
优化后的optimized_bubble_sort函数显著提升了冒泡排序算法的性能。通过引入一个名为swapped的标志位，这种优化允许算法在完成所有 N -1次遍历之前提前检测列表是否已经排序。当一次遍历完成且没有任何交换发生时，这清楚地表明列表已经排序完毕，算法可以提前退出。因此，尽管对于完全未排序或逆序列表，最坏情况下的时间复杂度仍然为 O ( N 2 )，但由于这种优化，对于已排序列表，最佳情况下的时间复杂度则提高到 O ( N )。
实质上，尽管这两个函数在最坏情况下的时间复杂度都是 O ( N 2 )，但优化后的optimized_bubble_sort在现实场景中有可能表现得更快，特别是在数据部分排序的情况下，使其成为传统冒泡排序算法的更高效版本。
冒泡排序算法的性能分析
很容易看出，冒泡排序涉及两层循环：
❑ 外部循环： 也称为 遍历 。例如，第一次遍历就是外部循环的第一次迭代。
❑ 内部循环： 当列表中剩余的未排序元素被排序直到最大值被移到右侧时进行。第一次遍历会进行 N -1次比较，第二次遍历会进行 N -2次比较，每次遍历都会减少一次比较次数。
冒泡排序算法的时间复杂度如下：
❑ 最佳情况： 如果列表已经排序（或几乎所有元素都已排序），则运行时间复杂度为 O (1)。
❑ 最坏情况： 如果没有或很少元素已排序，则最坏情况的运行时间复杂度为 O ( n 2 )，因为算法必须完全运行内部和外部循环。
现在让我们来看一下插入排序算法。
插入排序的基本思想是，在每次迭代中，我们都会从拥有的数据结构中取出一个数据点，然后将其插入到正确的位置，这就是为什么将其称为插入排序算法。
在第一次迭代中，我们选择两个数据点，并对它们进行排序，然后扩大选择范围，选择第三个数据点，并根据其值找到其正确的位置。该算法一直进行到所有的数据点都被移动到正确的位置。
这个过程如图3.2所示。
图3.2 插入排序算法
插入排序的Python代码如下所示：
在插入排序算法的核心循环中，我们从第二个元素（索引为1）开始遍历列表中的每个元素。对于每个元素，算法会检查前面的元素，以找到它在已排序子列表中的正确位置。这个检查是在条件elements[j]＞next_element中进行的，确保我们将当前的'next_element'放在列表已排序部分的适当位置上。
让我们来看一下插入排序算法的性能。
插入排序算法的性能分析
理解算法的效率对于确定其在不同应用中的适用性至关重要。让我们深入探讨插入排序的性能特征。
最佳情况
当输入数据已经排序时，插入排序展现出最佳的性能。在这种情况下，该算法能够高效地在线性时间内运行，表示为 O ( n )，其中 n 代表数据结构中的元素数量。
最坏情况
当输入数据按照相反顺序排列时，即最大的元素在最前面时，插入排序的效率会受到影响。在这种情况下，对于每个元素 i （其中 i 代表循环中当前元素的索引），内部循环可能需要移动几乎所有之前的元素。在这种情况下，插入排序的性能可以用一个二次函数来表示：
( w × i 2 )+( N × i )+ ϵ
式中， w 是权重因子，调整 i 2 的影响； N 代表随着输入规模的增大而扩展的系数； ϵ 通常代表其他项未涵盖的小的开销常数。
一般情况
一般来说，插入排序的平均性能往往是二次的，这对于较大的数据集可能会存在问题。
用例和建议
插入排序在以下情况下表现非常高效：
❑ 小型数据集。
❑ 几乎排序好的数据集，其中只有少量元素的顺序不正确。
然而，对于较大且更随机的数据集，推荐选择具有更好平均和最坏情况性能的排序算法，比如归并排序或快速排序。插入排序的二次时间复杂度使其在处理大规模数据时可扩展性较差。
归并排序在排序算法中独具特色，与冒泡排序和插入排序不同，它采用独特的方法。从历史上看，值得注意的是，John von Neumann在1940年引入了这种技术。虽然许多排序算法在部分排序的数据上表现得更好，但归并排序仍然不受影响；无论数据最初的排列方式如何，其性能始终保持一致。这种稳健性使得它成为处理大型数据集时的首选算法。
分治：归并排序的核心
归并排序采用分治策略，包括两个关键阶段——分割和合并：
1） 分割阶段： 与直接迭代列表不同，这个阶段通过递归将数据集分成两半。这种分割持续进行，直到每个部分达到最小尺寸（举例而言，可以是单个元素）。虽然将数据分割到如此细致的级别可能看起来有些反直觉，但这种粒度有助于在下一阶段进行有序合并。
2） 合并阶段： 在这里，先前分割的部分被系统地合并。算法不断处理和组合这些部分，直到整个列表排序完成。
对于归并排序算法的可视化表示，请参考图3.3。
图3.3 归并排序算法
伪代码概述
在深入研究实际代码之前，让我们通过一些伪代码来理解它的逻辑：
该伪代码提供了算法步骤的概述：
1）围绕中心midPoint将列表划分。
2）递归地划分，直到每个部分只有一个元素。
3）将排序好的部分系统地合并成一个完整的排序列表。
Python实现
这是归并排序算法的Python实现：
冒泡排序算法比较相邻元素，如果它们的顺序不正确，则交换它们的位置。另外，插入排序算法通过逐个转移元素来创建有序列表。如果我们有一个部分有序的列表，插入排序应该会表现得比较好。
但对于一个完全未排序的、大小为 N 的列表，冒泡排序需要完全遍历 N -1次才能将其完全排序。
丹诺德·希尔（Donald Shell）提出了希尔排序（以他的名字命名），该算法质疑了选择直接相邻的元素进行比较和交换的必要性。
现在，我们来理解这个概念。
在第一次遍历中，我们不是选择相邻的元素，而是使用固定间隔的元素，最终对由一对数据点组成的子列表进行排序。这在图3.4中有所展示。在第二次遍历中，它对包含四个数据点的子列表进行排序（见图3.4）。在随后的轮次中，每个子列表中的数据点数目不断增加，子列表的数量不断减少，直到最终只剩下一个包含所有数据点的子列表。此时，我们可以认为列表已经被排好序了。
图3.4 希尔排序算法的遍历
在Python中，用于实现希尔排序算法的代码如下：
我们可以看到，调用shell_sort函数成功地对输入数组进行了排序。
希尔排序算法的性能分析
可以观察到，在最坏情况下，希尔排序算法需要通过两个循环，使其具有 O ( n 2 )的时间复杂度。希尔排序不适用于大数据集，而是用于中等大小的数据集。粗略地说，在包含多达6000个元素的列表上，它的性能相当不错。如果数据部分正确排序，性能会更好。在最佳情况下，如果一个列表已经排序好了，它只需要一次遍历 N 个元素来验证顺序，从而实现 O ( N )的最佳性能。
正如我们在本章前面看到的那样，冒泡排序是最简单的排序算法之一。选择排序是对冒泡排序的改进，其目标是尽量减少算法所需的总交换次数。与冒泡排序算法的 N -1轮遍历过程相比，选择排序在每轮遍历中仅产生一次交换。与冒泡排序中将最大值逐步向顶部移动（得到 N -1次交换）不同，我们在选择排序中每次遍历时寻找最大值并将其向顶部移动。因此，在第一次遍历后，最大值将位于顶部。第二次遍历后，第二大的值将位于顶部值旁边。随着算法的进行，后续值将根据其值移动到其正确位置。最后一个值将在第（ N -1）次遍历后移动。因此，选择排序同样需要 N -1次遍历才能对 N 个数据项进行排序，如图3.5所示。
图3.5 选择排序算法
这里展示了选择排序在Python中的实现：
选择排序算法的性能分析
选择排序的最坏时间复杂度是 O ( N 2 )。请注意，其最坏性能近似于冒泡排序，因此不应该用于对较大的数据集进行排序。不过，选择排序仍是比冒泡排序设计得更好的算法，由于交换次数减少，其平均复杂度比冒泡排序好。
在排序算法中，并没有一种适合所有情况的解决方案。最佳选择通常取决于围绕你的数据的特定情况，比如数据的规模和当前状态。在这里，我们将深入探讨如何做出明智的决定，并举一些现实世界的例子。
规模小且已排序列表
对于规模小的数据集，特别是已经有序的数据，部署复杂的算法通常是不划算的。虽然像归并排序这样的算法无疑是强大的，但对于小数据量，其复杂性可能会掩盖其好处。
现实生活中的例子：想象一下按照作者姓氏对书架上的几本书进行排序。仅仅通过扫描并手动重新排列它们（类似于冒泡排序）比使用详细的排序方法更简单更快。
部分排序的数据
处理已经有些组织的数据时，像插入排序这样的算法会表现出色。它们利用现有的顺序，提高了效率。
现实生活中的例子：考虑一种课堂情景。如果学生按身高排队，但有几个略微错位，老师可以轻松发现并调整这些小的差异（类似于插入排序），而不必重新整理整个队伍。
大规模数据集
对于庞大的数据，其中数据量巨大可能会让人望而却步，归并排序被证明是一个可靠的选择。它的分治策略能够高效地处理大型列表，因此备受行业青睐。
现实生活中的例子：想象一下一个庞大的图书馆，每天都收到成千上万本书。按出版日期或作者对它们进行排序需要系统化的方法。在这种情况下，像归并排序这样将任务分解为可管理的块的方法是非常宝贵的。
许多计算任务的核心需求是：在复杂的数据结构中定位特定的数据。表面上，最简单的方法可能是扫描每个数据点，直到找到目标。但是，随着数据量的增加，我们可以想象到，这种方法会逐渐失去效率。
搜索为何如此关键呢？无论是用户查询数据库、系统访问文件，还是应用程序获取特定数据，高效的搜索决定了这些操作的速度和响应能力。如果没有熟练的搜索技术，系统可能会变得迟缓，特别是在数据量不断增加的情况下。
随着对数据快速检索的需求增加，复杂搜索算法的作用变得不可忽视。它们提供了浏览大量数据所需的灵活性和效率，确保系统保持灵活，并且用户得到满足。因此，搜索算法就像是数字领域的导航员，引导我们在信息海洋中找到我们寻找的精确数据。
本节介绍了以下搜索算法：
❑ 线性搜索
❑ 二分搜索
❑ 插值搜索
让我们更详细地看看它们各自的情况。
线性搜索是一种简单的搜索数据的策略，其方法是简单地循环遍历每个元素，查找目标。每个数据点都被搜索以寻找匹配项，当找到匹配项时，结果被返回，算法退出循环。否则，算法会继续搜索直到达到数据的末尾。线性搜索的明显缺点是由于固有的穷举搜索，速度非常慢。其优点是数据不需要像本章介绍的其他算法那样需要排序。
让我们来看看线性搜索的代码：
现在，查看一下前面代码的输出：
请注意，运行linear_search函数将在成功找到数据时返回True值。
线性搜索的性能分析
如上所述，线性搜索是一种执行穷举搜索的简单算法，其最坏时间复杂度是 O ( N )。更多信息请在https://wiki.python.org/moin/TimeComplexity上获得。
二分搜索算法的前提条件是数据必须是有序的。该算法反复将一个列表分成两部分，并跟踪最低和最高的索引，直到找到它要找的值为止。
输出结果如下：
请注意，调用binary_search函数将在输入列表中找到值时返回True值。
二分搜索算法的性能分析
二分搜索之所以如此命名，是因为在每次迭代中，算法都会将数据分成两部分。如果数据有 N 项，它最多需要 O (log N )步来完成迭代，这意味着算法的运行时间为 O (log N )。
二分搜索基于将数据集中心作为关键点进行搜索。而插值搜索更为复杂。它利用目标值来估计已排序数组中元素的位置。让我们通过一个示例来理解它。假设我们想在英文字典中搜索一个单词，比如“river”。我们将利用这个信息进行插值，并从以字母“r”开头的单词开始搜索。一个更加通用的插值搜索可以按照以下方式编程：
输出结果如下：
请注意，在使用int_polsearch函数之前，首先需要使用排序算法对数组进行排序。
插值搜索算法的性能
如果数据分布不均匀，则插值搜索算法的性能会很差，该算法最坏时间复杂度是 O ( N )。如果数据分布得相当均匀，则最好时间复杂度是 O (log(log N ))。
在给定的数据存储库中高效、准确地搜索数据的能力对许多现实生活中的应用至关重要。根据你所选择的搜索算法，你可能还需要先对数据进行排序。选择恰当的排序和搜索算法将取决于数据的类型和规模以及你要求解的问题的性质。
让我们尝试使用本章介绍的算法来解决某国移民部门将一个新的申请人与历史记录进行匹配的问题。当有人申请签证进入该国时，系统会尝试将申请人与现有的历史记录进行匹配。如果找到至少一个匹配项，则系统会进一步计算此人过去被批准或被拒绝的次数。另外，如果没有找到匹配的记录，系统会将申请人归类为新的申请人，并向他们发出一个新的识别码。
在历史数据中搜索、定位和识别一个人的能力对系统至关重要。这一信息很重要，因为如果某人在过去申请过，并且知道申请被拒绝了，那么这可能会对此人当前的申请产生负面影响。同样，如果某人的申请在过去被批准过，则该项批准可能会增加此人当前申请获得批准的机会。通常情况下，历史数据库将有数百万行，因此我们需要一个精心设计的解决方案来匹配历史数据库中的新申请人。
让我们假设数据库中的历史表如下所示。
在此表中，第一列Personal ID与历史数据库中每个唯一的申请人相关联。如果历史数据库中有3000万个唯一的申请人，那么将有3000万个唯一的Personal ID。每个Personal ID都在历史数据库系统中标识一个申请人。
第二列是Application ID，每个Application ID都标识了系统中唯一的申请。一个人可能在过去申请过不止一次，因此，这意味着在历史数据库中，我们所拥有的不同的Application ID会比Personal ID多。如上表所示，John Doe只有一个Personal ID，却有两个Application ID。
上表只显示了历史数据集的一个样本。假设我们的历史数据集有近100万行，其中包含了过去10年的申请人记录。新的申请人以平均每分钟约2个申请人的速度不断到来。对于每个申请人，我们需要完成以下工作：
❑ 为申请人发放新的Application ID。
❑ 查看历史数据库中是否有匹配的申请人。
❑ 如果找到了匹配的申请人，则使用历史数据库中找到的该申请人的Personal ID。我们还需要确定历史数据库中已批准或拒绝该申请人的次数。
❑ 如果没有找到匹配的申请人，那么我们则需要为这个人发放新的Personal ID。
假设一个申请人带着以下凭证来到这里：
❑ First Name:John
❑ Surname:Doe
❑ DOB:2000-09-19
现在，我们如何设计一个能够进行高效而低成本搜索的应用呢？
在数据库中搜索新的申请人的一种策略可以设计如下：
❑ 按照DOB（出生日期）对历史数据库进行排序。
❑ 每次有申请人到达时，向申请人发放新的申请ID。
❑ 取出所有符合该出生日期的记录，这将是主要的查找过程。
❑ 在匹配的记录中，使用名字（First Name）和姓氏（Last Name）进行二次查找。
❑ 如果找到匹配的申请人，用Personal ID来指代该申请人，计算该申请人被批准和拒绝的次数。
❑ 如果没有找到匹配项，则向该申请人发放新的Personal ID。
我们尝试选择合适的算法对历史数据库进行排序。我们可以放心地排除冒泡排序，因为数据量很大。希尔排序有更好的表现，但前提是列表已经被部分排好序。因此，归并排序可能是对历史数据库进行排序的最佳选择。
当一个申请人到来时，我们需要在历史数据库中搜索并定位这个人。由于数据已经进行了排序，因此可以使用插值搜索或二分搜索。由于是按照DOB（出生日期）进行排序的，申请人很可能会均匀分布，所以我们可以放心地使用插值搜索。
我们先基于DOB（出生日期）进行搜索，返回一组具有相同出生日期的申请人。现在，我们需要在具有相同出生日期的一小部分人中找到所需的人。由于我们已经成功地将数据缩小为一个小的子集，因此可以使用任何搜索算法（包括线性搜索）来搜索申请人。请注意，我们在这里稍微简化了二次搜索问题。如果找到多个匹配项，我们还需要通过汇总搜索结果来计算被批准和拒绝的总数。
在现实世界中，由于名字和姓氏的拼写可能略有不同，因此在二次搜索中需要使用某种模糊搜索算法来识别每个人。搜索中可能需要使用某种距离算法来实现模糊搜索，比如相似度超过规定阈值的数据点将被认为是同一个人。
本章介绍了一组排序和搜索算法，还讨论了不同排序和搜索算法的优缺点。我们对这些算法的性能进行了量化，并了解了每种算法应该在什么时候使用。
在接下来的章节中，我们将学习动态算法。我们还将看一个实际设计算法的例子以及页面排序算法的详细内容。最后，我们将研究线性规划算法。