Python 数据结构和算法实用指南（三）（2）https://developer.aliyun.com/article/1507581
第九章：搜索
所有数据结构中最重要的操作之一是从存储的数据中搜索元素。有各种方法可以在数据结构中搜索元素；在本章中，我们将探讨可以用来在项目集合中查找元素的不同策略。
搜索操作对于排序非常重要。如果没有使用某种搜索操作的变体，几乎不可能对数据进行排序。如果搜索算法有效，排序算法将会很快。在本章中，我们将讨论不同的搜索算法。
搜索操作的性能受到即将搜索的项目是否已经排序的影响，我们将在后续章节中看到。
在本章结束时，您将能够做到以下事情：
- 了解各种搜索算法
- 了解流行搜索算法的实现
- 了解二分搜索算法的实现
- 了解插值的实现
技术要求
本章中使用的源代码可在以下 GitHub 链接找到：github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Python-3.7-Second-Edition/tree/master/Chapter09。
搜索简介
搜索算法分为两种类型：
- 将搜索算法应用于已经排序的项目列表；即应用于有序的项目集
- 将搜索算法应用于未排序的项目集
线性搜索
搜索操作是为了从存储的数据中找出给定的项目。如果存储的列表中存在搜索的项目，则返回其所在的索引位置，否则返回未找到该项目。在列表中搜索项目的最简单方法是线性搜索方法，其中我们在整个列表中逐个查找项目。
让我们以5个列表项{60, 1, 88, 10, 11, 100}为例，以了解线性搜索算法，如下图所示：
前面的列表中的元素可以通过列表索引访问。为了在列表中找到一个元素，我们使用线性搜索技术。该技术通过使用索引遍历元素列表，从列表的开头移动到末尾。每个元素都会被检查，如果它与搜索项不匹配，则会检查下一个项目。通过从一个项目跳到下一个项目，列表被顺序遍历。
本章中使用整数值的列表项来帮助您理解概念，因为整数可以很容易地进行比较；但是，列表项也可以保存任何其他数据类型。
无序线性搜索
线性搜索方法取决于列表项的存储方式-它们是否按顺序排序或无序存储。让我们首先看看列表是否包含未排序的项目。
考虑一个包含元素 60、1、88、10 和 100 的列表-一个无序列表。列表中的项目没有按大小排序。要在这样的列表上执行搜索操作，首先从第一个项目开始，将其与搜索项进行比较。如果搜索项不匹配，则检查列表中的下一个元素。这将继续进行，直到我们到达列表中的最后一个元素或找到匹配项为止。
以下是 Python 中对无序项目列表进行线性搜索的实现：
def search(unordered_list, term): unordered_list_size = len(unordered_list) for i in range(unordered_list_size): if term == unordered_list[i]: return i return None
search函数接受两个参数；第一个是保存我们数据的列表，第二个参数是我们正在寻找的项目，称为搜索项。
获取数组的大小并确定for循环执行的次数。以下代码描述了这一点：
if term == unordered_list[i]: ...
在for循环的每次通过中，我们测试搜索项是否等于索引项。如果为真，则表示匹配，无需继续搜索。我们返回在列表中找到搜索项的索引位置。
如果循环运行到列表的末尾而没有找到匹配项，则返回None，表示列表中没有这样的项目。
在无序的项目列表中，没有指导规则来插入元素。因此，它影响了搜索的执行方式。因此，我们必须依次访问列表中的所有项目。如下图所示，对术语66的搜索从第一个元素开始，并移动到列表中的下一个元素。
因此，首先将60与66进行比较，如果不相等，我们将66与下一个元素1进行比较，然后是88，依此类推，直到在列表中找到搜索项为止：
无序线性搜索的最坏情况运行时间为O(n)。在找到搜索项之前，可能需要访问所有元素。最坏情况是搜索项位于列表的最后位置。
有序线性搜索
线性搜索的另一种情况是，当列表元素已经排序时，我们的搜索算法可以得到改进。假设元素已按升序排序，则搜索操作可以利用列表的有序性使搜索更加高效。
算法简化为以下步骤：
- 按顺序移动列表
- 如果搜索项大于循环中当前检查的对象或项，则退出并返回
None
在遍历列表的过程中，如果搜索项大于当前项，则无需继续搜索。
让我们考虑一个示例来看看这是如何工作的。我们拿一个项目列表，如下图所示，并且我们想搜索术语5：
当搜索操作开始并且第一个元素与搜索项（5）进行比较时，找不到匹配项。但是，列表中还有更多元素，因此搜索操作继续检查下一个元素。在排序列表中继续前进的更有力的原因是，我们知道搜索项可能与大于2的任何元素匹配。
经过第四次比较，我们得出结论，搜索项无法在列表中后面的任何位置找到6所在的位置。换句话说，如果当前项大于搜索项，则表示无需进一步搜索列表。
以下是列表已排序时线性搜索的实现：
def search(ordered_list, term): ordered_list_size = len(ordered_list) for i in range(ordered_list_size): if term == ordered_list[i]: return i elif ordered_list[i] > term: return None return None
在上述代码中，if语句现在用于检查搜索项是否在列表中找到。elif测试条件为ordered_list[i] > term。如果比较结果为True，则该方法返回None。
方法中的最后一行返回None，因为循环可能会遍历列表，但搜索项仍未在列表中匹配。
有序线性搜索的最坏情况时间复杂度为O(n)。一般来说，这种搜索被认为是低效的，特别是在处理大型数据集时。
二进制搜索
二进制搜索是一种搜索策略，用于在排序的数组或列表中查找元素；因此，二进制搜索算法从给定的排序项目列表中找到给定的项目。这是一种非常快速和高效的搜索元素的算法，唯一的缺点是我们需要一个排序的列表。二进制搜索算法的最坏情况运行时间复杂度为O(log n)，而线性搜索的复杂度为O(n)。
二分搜索算法的工作方式如下。它通过将给定的列表分成两半来开始搜索项。如果搜索项小于中间值，则只在列表的前半部分查找搜索项，如果搜索项大于中间值，则只在列表的后半部分查找。我们重复相同的过程，直到找到搜索项或者我们已经检查了整个列表。
让我们通过一个例子来理解二分搜索。假设我们有一本 1000 页的书，我们想找到第 250 页。我们知道每本书的页码是从1开始顺序编号的。因此，根据二分搜索的类比，我们首先检查搜索项 250，它小于 500（书的中点）。因此，我们只在书的前半部分搜索所需的页面。然后我们再次看到书的前半部分的中点，即使用 500 页作为参考，我们找到中点，即 250。这使我们更接近找到第 250 页。然后我们在书中找到所需的页面。
让我们考虑另一个例子来理解二分搜索的工作原理。我们想从包含 12 个项的列表中搜索43，如下图所示：
我们通过将其与列表的中间项进行比较来开始搜索项，例如在示例中是37。如果搜索项小于中间值，则只查看列表的前半部分；否则，我们将查看另一半。因此，我们只需要在列表的后半部分搜索项。我们遵循相同的概念，直到在列表中找到搜索项43，如前图所示。
以下是对有序物品列表进行二分搜索算法的实现：
def binary_search(ordered_list, term): size_of_list = len(ordered_list) - 1 index_of_first_element = 0 index_of_last_element = size_of_list while index_of_first_element <= index_of_last_element: mid_point = (index_of_first_element + index_of_last_element)//2 if ordered_list[mid_point] == term: return mid_point if term > ordered_list[mid_point]: index_of_first_element = mid_point + 1 else: index_of_last_element = mid_point - 1 if index_of_first_element > index_of_last_element: return None
假设我们要找到列表中10的位置如下：
该算法使用while循环来迭代地调整列表中的限制，以便找到搜索项。停止while循环的终止条件是起始索引index_of_first_element和index_of_last_element索引之间的差值应为正数。
该算法首先通过将第一个元素的索引（0）加上最后一个元素的索引（4）并除以2来找到列表的中点，mid_point：
mid_point = (index_of_first_element + index_of_last_element)//2
在这种情况下，中点是100，值10不在列表的中间位置找到。由于我们正在搜索10，它小于中点，因此它位于列表的前半部分，因此，我们将索引范围调整为index_of_first_element到mid_point-1，如下图所示。然而，如果我们正在搜索120，在这种情况下，由于 120 大于中间值（100），我们将在列表的后半部分搜索项，并且我们需要将列表索引范围更改为mid_point +1到index_of_last_element。如下图所示：
现在我们的index_of_first_element和index_of_last_element的新索引分别为0和1，我们计算中点(0 + 1)/2，得到0。新的中点是0，因此我们找到中间项并将其与搜索项进行比较，ordered_list[0]，得到值10。现在我们找到了搜索项，并返回索引位置。
通过调整index_of_first_element和index_of_last_element的索引，我们将列表大小减半，只要index_of_first_element小于index_of_last_element。当这种情况不再成立时，很可能是我们要搜索的项不在列表中。
我们讨论的实现是迭代的。我们也可以通过应用相同的原则并移动标记搜索列表开头和结尾的指针来开发算法的递归变体。考虑以下代码：
def binary_search(ordered_list, first_element_index, last_element_index, term): if (last_element_index < first_element_index): return None else: mid_point = first_element_index + ((last_element_index - first_element_index) // 2) if ordered_list[mid_point] > term: return binary_search(ordered_list, first_element_index, mid_point-1,term) elif ordered_list[mid_point] < term: return binary_search(ordered_list, mid_point+1, last_element_index, term) else: return mid_point
对二分搜索算法的递归实现的调用及其输出如下：
store = [2, 4, 5, 12, 43, 54, 60, 77] print(binary_search(store, 0, 7, 2)) Output: >> 0
在这里，递归二分搜索和迭代二分搜索之间唯一的区别是函数定义，以及计算mid_point的方式。在((last_element_index - first_element_index) // 2)操作之后，mid_point的计算必须将其结果加到first_element_index上。这样，我们定义了尝试搜索的列表部分。
二分搜索算法的最坏情况时间复杂度为O(log n)。每次迭代中列表的一半遵循元素数量和它们的进展的log(n)。
不言而喻，log x假定是指以 2 为底的对数。
插值搜索
插值搜索算法是二分搜索算法的改进版本。当排序列表中的元素均匀分布时，它的性能非常高。在二分搜索中，我们总是从列表的中间开始搜索，而在插值搜索中，我们根据要搜索的项确定起始位置。在插值搜索算法中，起始搜索位置很可能最接近列表的开头或结尾，具体取决于搜索项。如果搜索项接近列表中的第一个元素，则起始搜索位置很可能靠近列表的开头。
插值搜索是二分搜索算法的另一种变体，与人类在任何项目列表上执行搜索的方式非常相似。它基于尝试猜测在排序项目列表中可能找到搜索项的索引位置。它的工作方式类似于二分搜索算法，只是确定分割标准以减少比较次数的方法不同。在二分搜索的情况下，我们将数据分成相等的两部分，在插值搜索的情况下，我们使用以下公式来分割数据：
mid_point = lower_bound_index + (( upper_bound_index - lower_bound_index)// (input_list[upper_bound_index] - input_list[lower_bound_index])) * (search_value - input_list[lower_bound_index])
在上述公式中，lower_bound_index变量是下界索引，即列表中最小值的索引，upper_bound_index表示列表中最大值的索引位置。input_list[lower_bound_index]和input_list[lower_bound_index]变量分别是列表中的最小值和最大值。search_term变量包含要搜索的项的值。
让我们通过以下包含 7 个项目的列表来考虑一个示例，以了解插值搜索算法的工作原理：
为了找到120，我们知道应该查看列表的右侧部分。我们对二分搜索的初始处理通常会首先检查中间元素，以确定是否与搜索项匹配。
更像人类的方法是选择一个中间元素，以便不仅将数组分成两半，而且尽可能接近搜索项。中间位置是使用以下规则计算的：
mid_point = (index_of_first_element + index_of_last_element)//2
在插值搜索算法的情况下，我们将用更好的公式替换这个公式，以使我们更接近搜索项。mid_point将接收nearest_mid函数的返回值，该值是使用以下方法计算的：
def nearest_mid(input_list, lower_bound_index, upper_bound_index, search_value): return lower_bound_index + (( upper_bound_index -lower_bound_index)// (input_list[upper_bound_index] -input_list[lower_bound_index])) * (search_value -input_list[lower_bound_index])
nearest_mid函数的参数是要进行搜索的列表。lower_bound_index和upper_bound_index参数表示希望在列表中找到搜索项的范围。此外，search_value表示正在搜索的值。
给定我们的搜索列表，44，60，75，100，120，230和250，nearest_mid将使用以下值进行计算：
lower_bound_index = 0 upper_bound_index = 6 input_list[upper_bound_index] = 250 input_list[lower_bound_index] = 44 search_value = 230
让我们计算mid_point的值：
mid_point= 0 + (6-0)//(250-44) * (230-44) = 5
现在可以看到mid_point的值将接收值5。因此，在插值搜索的情况下，算法将从索引位置5开始搜索，这是我们搜索词的位置索引。因此，要搜索的项将在第一次比较中找到，而在二分搜索的情况下，我们将选择100作为mid_point，这将需要再次运行算法。
以下是一个更直观的例子，说明了典型的二分搜索与插值搜索的不同之处。在典型的二分搜索中，它找到了看起来在列表中间的中点：
在插值搜索中，中点通常更靠左或更靠右。这是由于在除法时使用的乘数的影响。在前面的图表中，我们的中点已经向右倾斜。
插值算法的实现与二分搜索的实现相同，只是我们计算中点的方式不同。
在这里，我们提供了插值搜索算法的实现，如下所示的代码：
def interpolation_search(ordered_list, term): size_of_list = len(ordered_list) - 1 index_of_first_element = 0 index_of_last_element = size_of_list while index_of_first_element <= index_of_last_element: mid_point = nearest_mid(ordered_list, index_of_first_element, index_of_last_element, term) if mid_point > index_of_last_element or mid_point < index_of_first_element: return None if ordered_list[mid_point] == term: return mid_point if term > ordered_list[mid_point]: index_of_first_element = mid_point + 1 else: index_of_last_element = mid_point - 1 if index_of_first_element > index_of_last_element: return None
nearest_mid函数使用乘法运算。这可能会产生大于upper_bound_index或小于lower_bound_index的值。当发生这种情况时，意味着搜索词term不在列表中。因此，返回None表示这一点。
那么当ordered_list[mid_point]不等于搜索词时会发生什么呢？好吧，我们现在必须重新调整index_of_first_element和index_of_last_element，以便算法将专注于可能包含搜索词的数组部分。这与我们在二分搜索中所做的事情完全相同：
if term > ordered_list[mid_point]: index_of_first_element = mid_point + 1
如果搜索词大于ordered_list[mid_point]存储的值，那么我们只需调整index_of_first_element变量，指向mid_point + 1索引。
以下图表显示了调整的过程。index_of_first_element被调整并指向mid_point+1索引：
图表只是说明了中点的调整。在插值搜索中，中点很少将列表分成两个完全相等的部分。
另一方面，如果搜索词小于ordered_list[mid_point]存储的值，那么我们只需调整index_of_last_element变量，指向索引mid_point - 1。这个逻辑在 if 语句的 else 部分中体现：index_of_last_element = mid_point - 1。
图表显示了对index_of_last_element的重新计算对中点位置的影响。
让我们用一个更实际的例子来理解二分搜索和插值搜索算法的内部工作原理。
例如，考虑以下元素列表：
[ 2, 4, 5, 12, 43, 54, 60, 77]
在索引 0 处存储值 2，在索引 7 处存储值 77。现在，假设我们要在列表中找到元素 2。这两种不同的算法将如何处理？
如果我们将这个列表传递给interpolation search函数，那么nearest_mid函数将使用mid_point计算公式返回等于0的值：
mid_point= 0 + (7-0)//(77-2) * (2-2) = 0
当我们得到mid_point值0时，我们从索引0开始插值搜索。只需一次比较，我们就找到了搜索项。
另一方面，二分搜索算法需要三次比较才能找到搜索项，如下图所示：
![
计算得到的第一个mid_point值为3。第二个mid_point值为1，最后一个mid_point值为搜索项所在的0。
因此，很明显，插值搜索算法在大多数情况下比二分搜索效果更好。
选择搜索算法
与有序和无序线性搜索函数相比，二分搜索和插值搜索算法在性能上更好。由于有序和无序线性搜索在列表中顺序探测元素以找到搜索项，因此其时间复杂度为O(n)。当列表很大时，性能非常差。
另一方面，二分搜索操作在每次搜索尝试时都会将列表切成两半。在每次迭代中，我们比线性策略更快地接近搜索项。时间复杂度为O(log n)。尽管使用二分搜索可以获得速度上的优势，但其主要缺点是不能应用于未排序的项目列表，也不建议用于小型列表，因为排序的开销很大。
能够到达包含搜索项的列表部分在很大程度上决定了搜索算法的性能。在插值搜索算法中，中点的计算方式使得更有可能更快地获得我们的搜索项。插值搜索的平均情况时间复杂度为O(log(log n))，而最坏情况时间复杂度为O(n)。这表明插值搜索比二分搜索更好，并在大多数情况下提供更快的搜索。
总结
在本章中，我们讨论了两种重要的搜索算法类型。讨论了线性和二分搜索算法的实现以及它们的比较。本章还详细讨论了二分搜索变体插值搜索。
在下一章中，我们将使用搜索算法的概念进行排序算法。我们还将利用已经获得的知识对项目列表执行排序算法。
第十章：排序
排序意味着重新组织数据，使其按从小到大的顺序排列。排序是数据结构和计算中最重要的问题之一。数据在排序之前经常被排序，因为这样可以非常高效地检索，无论是一组姓名、电话号码，还是简单待办事项清单上的项目。
在本章中，我们将学习一些最重要和流行的排序技术，包括以下内容：
- 冒泡排序
- 插入排序
- 选择排序
- 快速排序
- 堆排序
在本章中，我们通过考虑它们的渐近行为来比较不同的排序算法。一些算法相对容易开发，但性能可能较差，而其他算法在实现上稍微复杂一些，但在对长列表进行排序时表现良好。
排序后，对一组项目进行搜索操作变得更加容易。我们将从最简单的排序算法开始；即冒泡排序算法。
技术要求
用于解释本章概念的所有源代码都在以下 GitHub 存储库中提供：github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Python-Second-Edition/tree/master/Chapter10。
排序算法
排序意味着将列表中的所有项目按其大小的升序排列。我们将讨论一些最重要的排序算法，它们各自具有不同的性能属性，涉及运行时复杂性。排序算法根据它们的内存使用、复杂性、递归性以及它们是否基于比较等考虑进行分类。
一些算法使用更多的 CPU 周期，因此具有糟糕的渐近值。其他算法在对一些值进行排序时会消耗更多的内存和其他计算资源。另一个考虑因素是排序算法如何适合递归、迭代或两者表达。有些算法使用比较作为排序元素的基础。冒泡排序算法就是一个例子。非比较排序算法的例子包括桶排序和鸽巢排序算法。
冒泡排序算法
冒泡排序算法的思想非常简单。给定一个无序列表，我们比较列表中相邻的元素，每次比较后，将它们按大小顺序放置。这是通过交换相邻的项目来实现的，如果它们的顺序不正确。这个过程对于 n 个项目的列表会重复 n-1 次。在每次迭代中，最大的元素都会被放在最后。例如，在第一次迭代中，最大的元素将被放在列表的最后位置，然后，相同的过程将对剩下的 n-1 个项目进行。在第二次迭代中，第二大的元素将被放在列表的倒数第二个位置，然后该过程将重复，直到列表排序完成。
让我们以只有两个元素{5, 2}的列表来理解冒泡排序的概念，如下图所示：
为了对这个列表进行排序，我们只需将值交换到正确的位置，2 占据索引0，5 占据索引1。为了有效地交换这些元素，我们需要一个临时存储区域：
冒泡排序算法的实现从交换方法开始，如前图所示。首先，元素5将被复制到临时位置temp。然后，元素2将被移动到索引0。最后，5将从 temp 移动到索引1。最终，元素将被交换。列表现在包含元素[2, 5]。以下代码将交换unordered_list[j]的元素与unordered_list[j+1]的元素，如果它们不按正确顺序排列的话：
temp = unordered_list[j] unordered_list[j] = unordered_list[j+1] unordered_list[j+1] = temp
现在我们已经能够交换一个包含两个元素的数组，使用相同的思路对整个列表进行排序应该很简单。
让我们考虑另一个例子，以了解冒泡排序算法对包含6个元素的无序列表进行排序的工作原理，例如{45，23，87，12，32，4}。在第一次迭代中，我们开始比较前两个元素45和23，并交换它们，因为45应该放在23之后。然后，我们比较下一个相邻值45和87，看它们是否按正确顺序排列。如果它们没有按正确顺序排列，则交换它们。我们可以看到，在冒泡排序的第一次迭代后，最大的元素87被放置在列表的最后位置：
第一次迭代后，我们只需要排列剩下的(n-1)个元素；我们通过比较剩下的五个元素的相邻元素来重复相同的过程。第二次迭代后，第二大的元素45被放置在列表中倒数第二个位置，如下图所示：
接下来，我们需要比较剩下的(n-2)个元素，将它们排列如下图所示：
同样地，我们比较剩下的元素来对它们进行排序：
最后，在剩下的两个元素中，我们将它们按正确顺序放置，以获得最终排序的列表，如下图所示：
冒泡排序算法的实现将在一个双嵌套循环中工作，其中内部循环重复比较和交换给定列表中每次迭代中的相邻元素，而外部循环则跟踪内部循环应重复多少次。内部循环的实现如下：
for j in range(iteration_number): if unordered_list[j] > unordered_list[j+1]: temp = unordered_list[j] unordered_list[j] = unordered_list[j+1] unordered_list[j+1] = temp
在实现冒泡排序算法时，了解循环需要运行多少次才能完成所有交换是很重要的。例如，要对一个包含三个数字的列表[3, 2, 1]进行排序，我们最多需要交换两次元素。这等于列表长度减 1，可以写成iteration_number = len(unordered_list)-1。我们减 1 是因为它确切地给出了需要运行的最大迭代次数。让我们通过以下示例来展示这一点，在一个包含 3 个数字的列表中，通过在恰好两次迭代中交换相邻元素，最大的数字最终位于列表的最后位置：
if语句确保如果两个相邻元素已经按正确顺序排列，则不会发生不必要的交换。内部for循环只会导致相邻元素的交换在我们的列表中确切地发生两次。
为了使整个列表排序，这个交换操作需要发生多少次？我们知道，如果我们重复整个交换相邻元素的过程多次，列表将被排序。外部循环用于实现这一点。列表中元素的交换导致以下动态：
我们意识到最多需要四次比较才能使我们的列表排序。因此，内部和外部循环都必须运行len(unordered_list)-1次，以便对所有元素进行排序，如下所示：
iteration_number = len(unordered_list)-1 for i in range(iteration_number): for j in range(iteration_number): if unordered_list[j] > unordered_list[j+1]: temp = unordered_list[j] unordered_list[j] = unordered_list[j+1] unordered_list[j+1] = temp
即使列表包含许多元素，也可以使用相同的原则。冒泡排序也有很多变体，可以最小化迭代和比较的次数。
例如，有一种冒泡排序算法的变体，如果在内部循环中没有交换，我们就会简单地退出整个排序过程，因为内部循环中没有任何交换操作表明列表已经排序。在某种程度上，这可以帮助加快算法的速度。
冒泡排序是一种低效的排序算法，其最坏情况和平均情况的运行时间复杂度为O(n²)，最佳情况的复杂度为O(n)。通常，不应该使用冒泡排序算法对大型列表进行排序。但是，在相对较小的列表上，它的性能还算不错。
插入排序算法
将相邻元素交换以对项目列表进行排序的想法也可以用于实现插入排序。插入排序算法维护一个始终排序的子列表，而列表的另一部分保持未排序。我们从未排序的子列表中取出元素，并将它们插入到排序的子列表的正确位置，使得这个子列表保持排序。
在插入排序中，我们从一个元素开始，假设它已经排序，然后从未排序的子列表中取出另一个元素，并将其放在排序的子列表中正确的位置（相对于第一个元素）。这意味着我们的排序子列表现在有两个元素。然后，我们再次从未排序的子列表中取出另一个元素，并将其放在排序的子列表中正确的位置（相对于已排序的两个元素）。我们反复遵循这个过程，将未排序的子列表中的所有元素一个接一个地插入到排序的子列表中。阴影元素表示有序子列表，在每次迭代中，未排序子列表中的一个元素被插入到排序子列表的正确位置。
让我们考虑一个例子来理解插入排序算法的工作原理。在我们的例子中，我们将对包含6个元素的列表{45, 23, 87, 12, 32, 4}进行排序。首先，我们从1个元素开始，假设它已经排序，然后从未排序的子列表中取出下一个元素23，并将其插入到排序的子列表中的正确位置。在下一次迭代中，我们从未排序的子列表中取出第三个元素87，并再次将其插入到排序的子列表中的正确位置。我们一直遵循相同的过程，直到所有元素都在排序的子列表中。整个过程如下图所示：
为了理解插入排序算法的实现，让我们以另一个包含5个元素的示例列表{5, 1, 100, 2, 10}为例，并用详细的解释来检查这个过程。
让我们考虑以下数组：
该算法通过使用for循环在1和4索引之间运行来开始。我们从索引1开始，因为我们假设索引0处的子数组已经按正确的顺序排序：
在循环执行的开始，我们有以下内容：
for index in range(1, len(unsorted_list)): search_index = index insert_value = unsorted_list[index]
在每次运行for循环的开始时，将unsorted_list[index]处的元素存储在insert_value变量中。稍后，当我们找到列表的排序部分中的适当位置时，insert_value将存储在该索引或位置上：
for index in range(1, len(unsorted_list)): search_index = index insert_value = unsorted_list[index] while search_index > 0 and unsorted_list[search_index-1] > insert_value : unsorted_list[search_index] = unsorted_list[search_index-1] search_index -= 1 unsorted_list[search_index] = insert_value
search_index用于向while循环提供信息；也就是说，确切地找到下一个需要插入到排序子列表中的元素的位置。
while循环向后遍历列表，受两个条件的指导：首先，如果search_index > 0，那么意味着在列表的排序部分中还有更多的元素；其次，while循环运行时，unsorted_list[search_index-1]必须大于insert_value变量。unsorted_list[search_index-1]数组将执行以下操作之一：
- 在
while循环第一次执行之前，指向unsorted_list[search_index]之前的一个元素 - 在
while循环第一次运行后，指向unsorted_list[search_index-1]之前的一个元素
在我们的示例列表中，while循环将被执行，因为5 > 1。在while循环的主体中，unsorted_list[search_index-1]处的元素存储在unsorted_list[search_index]处。search_index -= 1将列表向后遍历，直到它的值为0。
我们的列表现在如下所示：
在while循环退出后，search_index的最后已知位置（在这种情况下为0）现在帮助我们知道在哪里插入insert_value：
在for循环的第二次迭代中，search_index的值将为2，这是数组中第三个元素的索引。此时，我们从左向右（朝向索引0）开始比较。100将与5进行比较，但因为100大于5，while循环不会执行。100将被替换为它自己，因为search_index变量从未被减少。因此，unsorted_list[search_index] = insert_value将不会产生影响。
当search_index指向索引3时，我们将2与100进行比较，并将100移动到存储2的位置。然后我们将2与5进行比较，并将5移动到最初存储100的位置。此时，while循环将中断，2将存储在索引1中。数组将部分排序，值为[1, 2, 5, 100, 10]。
前面的步骤将为列表最后一次发生。
插入排序算法被认为是稳定的，因为它不会改变具有相等键的元素的相对顺序。它也只需要消耗列表占用的内存，因为它是原地交换的。
插入排序算法的最坏情况运行时间复杂度为**O(n²)**，最佳情况复杂度为O(n)。
Python 数据结构和算法实用指南（三）（4）https://developer.aliyun.com/article/1507589
