Python 入门指南（四）（2）https://developer.aliyun.com/article/1507401
选择搜索算法
二分搜索和插值搜索操作的性能比有序和无序线性搜索函数都要好。由于在列表中顺序探测元素以找到搜索项，有序和无序线性搜索的时间复杂度为O(n)。当列表很大时，这会导致性能非常差。
另一方面，二分搜索操作在尝试搜索时会将列表切成两半。在每次迭代中，我们比线性策略更快地接近搜索项。时间复杂度为O(log n)。尽管使用二分搜索可以获得速度上的提升，但它不能用于未排序的项目列表，也不建议用于小型列表。
能够找到包含搜索项的列表部分在很大程度上决定了搜索算法的性能。在插值搜索算法中，计算中间值以获得更高概率的搜索项。插值搜索的时间复杂度为O(log(log n))，这比其变体二分搜索更快。
摘要
在本章中，我们考察了两种搜索算法。讨论了线性搜索和二分搜索算法的实现以及它们的比较。本节还讨论了二分搜索变体——插值搜索。在接下来的章节中，知道使用哪种搜索操作将是相关的。
在下一章中，我们将利用所学知识对项目列表执行排序操作。
第十三章：排序
当收集到数据时，总会有必要对数据进行排序。排序操作对所有数据集都是常见的，无论是名称集合、电话号码还是简单的待办事项列表。
在本章中，我们将学习一些排序技术，包括以下内容：
- 冒泡排序
- 插入排序
- 选择排序
- 快速排序
- 堆排序
在我们对这些排序算法的处理中，我们将考虑它们的渐近行为。一些算法相对容易开发，但性能可能较差。其他一些稍微复杂的算法将表现出色。
排序后，对一组项目进行搜索操作变得更加容易。我们将从最简单的排序算法开始–冒泡排序算法。
排序算法
在本章中，我们将介绍一些排序算法，这些算法的实现难度各不相同。排序算法根据它们的内存使用、复杂性、递归性质、是否基于比较等等因素进行分类。
一些算法使用更多的 CPU 周期，因此具有较差的渐近值。其他算法在对一些值进行排序时会消耗更多的内存和其他计算资源。另一个考虑因素是排序算法如何适合递归或迭代表达。有些算法使用比较作为排序元素的基础。冒泡排序算法就是一个例子。非比较排序算法的例子包括桶排序和鸽巢排序。
冒泡排序
冒泡排序算法的思想非常简单。给定一个无序列表，我们比较列表中的相邻元素，每次只放入正确的大小顺序，只有两个元素。该算法依赖于一个交换过程。
取一个只有两个元素的列表：
要对这个列表进行排序，只需将它们交换到正确的位置，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
现在我们已经能够交换一个两元素数组，使用相同的思想对整个列表进行排序应该很简单。
我们将在一个双重嵌套循环中运行这个交换操作。内部循环如下：
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是因为它恰好给出了最大迭代次数：
通过在精确两次迭代中交换相邻元素，最大的数字最终位于列表的最后位置。
if 语句确保如果两个相邻元素已经按正确顺序排列，则不会发生不必要的交换。内部的 for 循环只会在我们的列表中精确发生两次相邻元素的交换。
然而，你会意识到第一次运行 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(n2)，最佳情况为 O(n)。通常情况下，不应该使用冒泡排序算法来对大型列表进行排序。然而，在相对较小的列表上，它的性能还是相当不错的。
有一种冒泡排序算法的变体，如果在内部循环中没有比较，我们就会简单地退出整个排序过程。在内部循环中不需要交换元素的情况下，表明列表已经排序好了。在某种程度上，这可以帮助加快通常被认为是缓慢的算法。
插入排序
通过交换相邻元素来对一系列项目进行排序的想法也可以用于实现插入排序。在插入排序算法中，我们假设列表的某个部分已经排序好了，而另一部分仍然未排序。在这种假设下，我们遍历列表的未排序部分，一次选择一个元素。对于这个元素，我们遍历列表的排序部分，并按正确的顺序将其插入，以使列表的排序部分保持排序。这是很多语法。让我们通过一个例子来解释一下。
考虑以下数组：
该算法首先使用 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)。
选择排序
另一个流行的排序算法是选择排序。这种排序算法简单易懂，但效率低下，其最坏和最佳渐近值为O(n²)。它首先找到数组中最小的元素，并将其与数据交换，例如，数组索引[0]处的数据。然后再次执行相同的操作；然而，在找到第一个最小元素后，列表剩余部分中的最小元素将与索引[1]处的数据交换。
为了更好地解释算法的工作原理，让我们对一组数字进行排序：
从索引0开始，我们搜索列表中在索引1和最后一个元素的索引之间存在的最小项。找到这个元素后，它将与索引0处找到的数据交换。我们只需重复此过程，直到列表变得有序。
在列表中搜索最小项是一个递增的过程：
对元素2和5进行比较，选择2作为较小的元素。这两个元素被交换。
交换操作后，数组如下所示：
仍然在索引0处，我们将2与65进行比较：
由于65大于2，所以这两个元素不会交换。然后在索引0处的元素2和索引3处的元素10之间进行了进一步的比较。不会发生交换。当我们到达列表中的最后一个元素时，最小的元素将占据索引0。
一个新的比较集将开始，但这一次是从索引1开始。我们重复整个比较过程，将存储在那里的元素与索引2到最后一个索引之间的所有元素进行比较。
第二次迭代的第一步将如下所示：
以下是选择排序算法的实现。函数的参数是我们想要按升序排列的未排序项目列表的大小：
def selection_sort(unsorted_list): size_of_list = len(unsorted_list) for i in range(size_of_list): for j in range(i+1, size_of_list): if unsorted_list[j] < unsorted_list[i]: temp = unsorted_list[i] unsorted_list[i] = unsorted_list[j] unsorted_list[j] = temp
算法从使用外部for循环开始遍历列表size_of_list，多次。因为我们将size_of_list传递给range方法，它将产生一个从0到size_of_list-1的序列。这是一个微妙的注释。
内部循环负责遍历列表，并在遇到小于unsorted_list[i]指向的元素时进行必要的交换。注意，内部循环从i+1开始，直到size_of_list-1。内部循环开始在i+1之间搜索最小的元素，但使用j索引：
上图显示了算法搜索下一个最小项的方向。
快速排序
快速排序算法属于分治算法类，其中我们将问题分解为更简单的小块来解决。在这种情况下，未排序的数组被分解成部分排序的子数组，直到列表中的所有元素都处于正确的位置，此时我们的未排序列表将变为已排序。
列表分区
在我们将列表分成更小的块之前，我们必须对其进行分区。这是快速排序算法的核心。要对数组进行分区，我们必须首先选择一个枢轴。数组中的所有元素将与此枢轴进行比较。在分区过程结束时，小于枢轴的所有元素将位于枢轴的左侧，而大于枢轴的所有元素将位于数组中枢轴的右侧。
枢轴选择
为了简单起见，我们将任何数组中的第一个元素作为枢轴。这种枢轴选择会降低性能，特别是在对已排序列表进行排序时。随机选择数组中间或最后一个元素作为枢轴也不会改善情况。在下一章中，我们将采用更好的方法来选择枢轴，以帮助我们找到列表中的最小元素。
实施
在深入代码之前，让我们通过使用快速排序算法对列表进行排序的步骤。首先要理解分区步骤非常重要，因此我们将首先解决该操作。
考虑以下整数列表。我们将使用以下分区函数对此列表进行分区：
def partition(unsorted_array, first_index, last_index): pivot = unsorted_array[first_index] pivot_index = first_index index_of_last_element = last_index less_than_pivot_index = index_of_last_element greater_than_pivot_index = first_index + 1 ...
分区函数接收我们需要分区的数组作为参数：其第一个元素的索引和最后一个元素的索引。
枢轴的值存储在pivot变量中，而其索引存储在pivot_index中。我们没有使用unsorted_array[0]，因为当调用未排序数组参数时，索引0不一定指向该数组中的第一个元素。枢轴的下一个元素的索引，first_index + 1，标记了我们开始在数组中寻找大于pivot的元素的位置，greater_than_pivot_index = first_index + 1。
less_than_pivot_index = index_of_last_element标记了列表中最后一个元素的位置，即我们开始搜索小于枢轴的元素的位置：
while True: while unsorted_array[greater_than_pivot_index] < pivot and greater_than_pivot_index < last_index: greater_than_pivot_index += 1 while unsorted_array[less_than_pivot_index] > pivot and less_than_pivot_index >= first_index: less_than_pivot_index -= 1
在执行主while循环之前，数组如下所示：
第一个内部while循环每次向右移动一个索引，直到落在索引2上，因为该索引处的值大于43。此时，第一个while循环中断并不再继续。在第一个while循环的条件测试中，只有当while循环的测试条件评估为True时，才会评估greater_than_pivot_index += 1。这使得对大于枢轴的元素的搜索向右侧的下一个元素进行。
第二个内部while循环每次向左移动一个索引，直到落在索引5上，其值20小于43：
此时，内部while循环都无法继续执行：
if greater_than_pivot_index < less_than_pivot_index: temp = unsorted_array[greater_than_pivot_index] unsorted_array[greater_than_pivot_index] = unsorted_array[less_than_pivot_index] unsorted_array[less_than_pivot_index] = temp else: break
由于greater_than_pivot_index < less_than_pivot_index，if 语句的主体交换了这些索引处的元素。else 条件在任何时候greater_than_pivot_index变得大于less_than_pivot_index时打破无限循环。在这种情况下，这意味着greater_than_pivot_index和less_than_pivot_index已经交叉。
我们的数组现在是这样的：
当less_than_pivot_index等于3且greater_than_pivot_index等于4时，执行 break 语句。
一旦我们退出while循环，我们就会交换unsorted_array[less_than_pivot_index]的元素和less_than_pivot_index的元素，后者作为枢轴的索引返回：
unsorted_array[pivot_index]=unsorted_array[less_than_pivot_index] unsorted_array[less_than_pivot_index]=pivot return less_than_pivot_index
下面的图片显示了代码在分区过程的最后一步中如何交换 4 和 43：
回顾一下，第一次调用快速排序函数时，它是围绕索引0的元素进行分区的。在分区函数返回后，我们得到数组[4, 3, 20, 43, 89, 77]。
正如你所看到的，元素43右边的所有元素都更大，而左边的元素更小。分区完成了。
使用分割点 43 和索引 3，我们将递归地对两个子数组[4, 30, 20]和[89, 77]进行排序，使用刚刚经历的相同过程。
主quick sort函数的主体如下：
def quick_sort(unsorted_array, first, last): if last - first <= 0: return else: partition_point = partition(unsorted_array, first, last) quick_sort(unsorted_array, first, partition_point-1) quick_sort(unsorted_array, partition_point+1, last)
quick sort函数是一个非常简单的方法，不超过 6 行代码。繁重的工作由partition函数完成。当调用partition方法时，它返回分区点。这是unsorted_array中的一个点，左边的所有元素都小于枢轴，右边的所有元素都大于它。
当我们在分区进度之后立即打印unsorted_array的状态时，我们清楚地看到了分区是如何进行的：
Output: [43, 3, 20, 89, 4, 77] [4, 3, 20, 43, 89, 77] [3, 4, 20, 43, 89, 77] [3, 4, 20, 43, 77, 89] [3, 4, 20, 43, 77, 89]
退一步，让我们在第一次分区发生后对第一个子数组进行排序。[4, 3, 20]子数组的分区将在greater_than_pivot_index在索引2和less_than_pivot_index在索引1时停止。在那一点上，两个标记被认为已经交叉。因为greater_than_pivot_index大于less_than_pivot_index，while循环的进一步执行将停止。枢轴 4 将与3交换，而索引1将作为分区点返回。
快速排序算法的最坏情况复杂度为O(n²)，但在对大量数据进行排序时效率很高。
堆排序
在第十一章中，图和其他算法，我们实现了（二叉）堆数据结构。我们的实现始终确保在元素被移除或添加到堆后，使用 sink 和 float 辅助方法来维护堆顺序属性。
堆数据结构可以用来实现称为堆排序的排序算法。回顾一下，让我们创建一个简单的堆，其中包含以下项目：
h = Heap() unsorted_list = [4, 8, 7, 2, 9, 10, 5, 1, 3, 6] for i in unsorted_list: h.insert(i) print("Unsorted list: {}".format(unsorted_list))
堆h被创建，并且unsorted_list中的元素被插入。在每次调用insert方法后，堆顺序属性都会通过随后调用float方法得到恢复。循环终止后，我们的堆顶部将是元素4。
我们堆中的元素数量是10。如果我们在堆对象h上调用pop方法 10 次并存储实际弹出的元素，我们最终得到一个排序好的列表。每次pop操作后，堆都会重新调整以保持堆顺序属性。
heap_sort方法如下：
class Heap: ... def heap_sort(self): sorted_list = [] for node in range(self.size): n = self.pop() sorted_list.append(n) return sorted_list
for循环简单地调用pop方法self.size次。循环终止后，sorted_list将包含一个排序好的项目列表。
insert方法被调用n次。与float方法一起，insert操作的最坏情况运行时间为O(n log n)，pop方法也是如此。因此，这种排序算法的最坏情况运行时间为O(n log n)。
总结
在本章中，我们探讨了许多排序算法。快速排序比其他排序算法表现要好得多。在讨论的所有算法中，快速排序保留了它所排序的列表的索引。在下一章中，我们将利用这一特性来探讨选择算法。
第十四章：选择算法
与在无序项目列表中查找元素相关的一组有趣的算法是选择算法。通过这样做，我们将回答与选择一组数字的中位数和选择列表中第 i 个最小或最大元素等问题有关的问题。
在本章中，我们将涵盖以下主题：
- 通过排序进行选择
- 随机选择
- 确定性选择
通过排序进行选择
列表中的项目可能会经历统计查询，如查找平均值、中位数和众数值。查找平均值和众数值不需要对列表进行排序。但是，要在数字列表中找到中位数，必须首先对列表进行排序。查找中位数需要找到有序列表中间位置的元素。但是，如果我们想要找到列表中的最后一个最小的项目或列表中的第一个最小的项目呢？
要找到无序项目列表中的第 i 个最小数字，重要的是要获得该项目出现的位置的索引。但是因为元素尚未排序，很难知道列表中索引为 0 的元素是否真的是最小的数字。
处理无序列表时要做的一个实际和明显的事情是首先对列表进行排序。一旦列表排序完成，就可以确保列表中的第零个元素将包含列表中的第一个最小元素。同样，列表中的最后一个元素将包含列表中的最后一个最小元素。
假设也许在执行搜索之前无法负担排序的奢侈。是否可能在不必首先对列表进行排序的情况下找到第 i 个最小的元素？
随机选择
在上一章中，我们研究了快速排序算法。快速排序算法允许我们对无序项目列表进行排序，但在排序算法运行时有一种保留元素索引的方式。一般来说，快速排序算法执行以下操作：
- 选择一个枢轴。
- 围绕枢轴对未排序的列表进行分区。
- 使用步骤 1和步骤 2递归地对分区列表的两半进行排序。
一个有趣且重要的事实是，在每个分区步骤之后，枢轴的索引在列表变得排序后也不会改变。正是这个属性使我们能够在一个不太完全排序的列表中工作，以获得第 i 个最小的数字。因为随机选择是基于快速排序算法的，它通常被称为快速选择。
快速选择
快速选择算法用于获取无序项目列表中的第 i 个最小元素，即数字。我们将算法的主要方法声明如下：
def quick_select(array_list, left, right, k): split = partition(array_list, left, right) if split == k: return array_list[split] elif split < k: return quick_select(array_list, split + 1, right, k) else: return quick_select(array_list, left, split-1, k)
quick_select函数的参数是列表中第一个元素的索引和最后一个元素的索引。第三个参数k指定了第 i 个元素。允许大于或等于零（0）的值，这样当k为 0 时，我们知道要在列表中搜索第一个最小的项目。其他人喜欢处理k参数，使其直接映射到用户正在搜索的索引，以便第一个最小的数字映射到排序列表的 0 索引。这都是个人偏好的问题。
对partition函数的方法调用，split = partition(array_list, left, right),返回split索引。split数组的这个索引是无序列表中的位置，其中right到split-1之间的所有元素都小于split数组中包含的元素，而split+1到left之间的所有元素都大于split数组中包含的元素。
当partition函数返回split值时，我们将其与k进行比较，以找出split是否对应于第 k 个项目。
如果split小于k，那么意味着第 k 个最小的项目应该存在或者在split+1和right之间被找到：
在前面的例子中，一个想象中的无序列表在索引 5 处发生了分割，而我们正在寻找第二小的数字。由于 5<2 为false，因此进行递归调用以搜索列表的另一半：quick_select(array_list, left, split-1, k)。
如果split索引小于k，那么我们将调用quick_select：
分区步骤
分区步骤与快速排序算法中的步骤完全相同。有几点值得注意：
def partition(unsorted_array, first_index, last_index): if first_index == last_index: return first_index pivot = unsorted_array[first_index] pivot_index = first_index index_of_last_element = last_index less_than_pivot_index = index_of_last_element greater_than_pivot_index = first_index + 1 while True: while unsorted_array[greater_than_pivot_index] < pivot and greater_than_pivot_index < last_index: greater_than_pivot_index += 1 while unsorted_array[less_than_pivot_index] > pivot and less_than_pivot_index >= first_index: less_than_pivot_index -= 1 if greater_than_pivot_index < less_than_pivot_index: temp = unsorted_array[greater_than_pivot_index] unsorted_array[greater_than_pivot_index] = unsorted_array[less_than_pivot_index] unsorted_array[less_than_pivot_index] = temp else: break unsorted_array[pivot_index] = unsorted_array[less_than_pivot_index] unsorted_array[less_than_pivot_index] = pivot return less_than_pivot_index
在函数定义的开头插入了一个 if 语句，以处理first_index等于last_index的情况。在这种情况下，这意味着我们的子列表中只有一个元素。因此，我们只需返回函数参数中的任何一个，即first_index。
总是选择第一个元素作为枢轴。这种选择使第一个元素成为枢轴是一个随机决定。通常不会产生良好的分割和随后的良好分区。然而，最终将找到第 i 个元素，即使枢轴是随机选择的。
partition函数返回由less_than_pivot_index指向的枢轴索引，正如我们在前一章中看到的。
从这一点开始，您需要用铅笔和纸跟随程序执行，以更好地了解如何使用分割变量来确定要搜索第 i 小项的列表的部分。
确定性选择
随机选择算法的最坏情况性能为O(n²)。可以改进随机选择算法的一部分以获得O(n)的最坏情况性能。这种算法称为确定性选择。
确定性算法的一般方法如下：
- 选择一个枢轴：
- 将无序项目列表分成每组五个元素。
- 对所有组进行排序并找到中位数。
- 递归重复步骤 1和步骤 2，以获得列表的真实中位数。
- 使用真实中位数来分区无序项目列表。
- 递归进入可能包含第 i 小元素的分区列表的部分。
枢轴选择
在随机选择算法中，我们选择第一个元素作为枢轴。我们将用一系列步骤替换该步骤，以便获得真实或近似中位数。这将改善关于枢轴的列表的分区：
def partition(unsorted_array, first_index, last_index): if first_index == last_index: return first_index else: nearest_median = median_of_medians(unsorted_array[first_index:last_index]) index_of_nearest_median = get_index_of_nearest_median(unsorted_array, first_index, last_index, nearest_median) swap(unsorted_array, first_index, index_of_nearest_median) pivot = unsorted_array[first_index] pivot_index = first_index index_of_last_element = last_index less_than_pivot_index = index_of_last_element greater_than_pivot_index = first_index + 1
现在让我们来研究分区函数的代码。nearest_median变量存储给定列表的真实或近似中位数：
def partition(unsorted_array, first_index, last_index): if first_index == last_index: return first_index else: nearest_median = median_of_medians(unsorted_array[first_index:last_index]) ....
如果unsorted_array参数只有一个元素，则first_index和last_index将相等。因此无论如何都会返回first_index。
然而，如果列表大小大于 1，我们将使用数组的部分调用median_of_medians函数，由first_index和last_index标记。返回值再次存储在nearest_median中。
中位数的中位数
median_of_medians函数负责找到任何给定项目列表的近似中位数。该函数使用递归返回真实中位数：
def median_of_medians(elems): sublists = [elems[j:j+5] for j in range(0, len(elems), 5)] medians = [] for sublist in sublists: medians.append(sorted(sublist)[len(sublist)/2]) if len(medians) <= 5: return sorted(medians)[len(medians)/2] else: return median_of_medians(medians)
该函数首先将列表elems分成每组五个元素。这意味着如果elems包含 100 个项目，则语句sublists = [elems[j:j+5] for j in range(0, len(elems), 5)]将创建 20 个组，每个组包含五个或更少的元素：
medians = [] for sublist in sublists: medians.append(sorted(sublist)[len(sublist)/2])
创建一个空数组并将其分配给medians，它存储分配给sublists的每个五个元素数组中的中位数。
for 循环遍历sublists中的列表列表。对每个子列表进行排序，找到中位数，并将其存储在medians列表中。
medians.append(sorted(sublist)[len(sublist)/2])语句将对列表进行排序，并获取存储在其中间索引的元素。这成为五个元素列表的中位数。由于列表的大小较小，使用现有的排序函数不会影响算法的性能。
我们从一开始就明白，我们不会对列表进行排序以找到第 i 小的元素，那么为什么要使用 Python 的排序方法呢？嗯，由于我们只对五个或更少的非常小的列表进行排序，因此该操作对算法的整体性能的影响被认为是可以忽略的。
此后，如果列表现在包含五个或更少的元素，我们将对medians列表进行排序，并返回位于其中间索引的元素：
if len(medians) <= 5: return sorted(medians)[len(medians)/2]
另一方面，如果列表的大小大于五，我们将再次递归调用median_of_medians函数，并向其提供存储在medians中的中位数列表。
例如，以下数字列表：
[2, 3, 5, 4, 1, 12, 11, 13, 16, 7, 8, 6, 10, 9, 17, 15, 19, 20, 18, 23, 21, 22, 25, 24, 14]
我们可以使用代码语句sublists = [elems[j:j+5] for j in range(0, len(elems), 5)]将此列表分成每个五个元素一组，以获得以下列表：
[[2, 3, 5, 4, 1], [12, 11, 13, 16, 7], [8, 6, 10, 9, 17], [15, 19, 20, 18, 23], [21, 22, 25, 24, 14]]
对每个五个元素的列表进行排序并获取它们的中位数，得到以下列表：
[3, 12, 9, 19, 22]
由于列表的大小为五个元素，我们只返回排序列表的中位数，或者我们将再次调用median_of_median函数。
分区步骤
现在我们已经获得了近似中位数，get_index_of_nearest_median函数使用first和last参数指示的列表边界：
def get_index_of_nearest_median(array_list, first, second, median): if first == second: return first else: return first + array_list[first:second].index(median)
如果列表中只有一个元素，我们再次只返回第一个索引。arraylist[first:second]返回一个索引为 0 到list-1大小的数组。当我们找到中位数的索引时，由于新的范围索引[first:second]代码返回，我们会丢失它所在的列表部分。因此，我们必须将arraylist[first:second]返回的任何索引添加到first中，以获得找到中位数的真实索引：
swap(unsorted_array, first_index, index_of_nearest_median)
然后，我们使用交换函数将unsorted_array中的第一个元素与index_of_nearest_median进行交换。
这里显示了交换两个数组元素的实用函数：
def swap(array_list, first, second): temp = array_list[first] array_list[first] = array_list[second] array_list[second] = temp
我们的近似中位数现在存储在未排序列表的first_index处。
分区函数将继续进行，就像快速选择算法的代码一样。分区步骤之后，数组看起来是这样的：
def deterministic_select(array_list, left, right, k): split = partition(array_list, left, right) if split == k: return array_list[split] elif split < k : return deterministic_select(array_list, split + 1, right, k) else: return deterministic_select(array_list, left, split-1, k)
正如您已经观察到的那样，确定选择算法的主要功能看起来与其随机选择对应物完全相同。在初始array_list围绕近似中位数进行分区后，将与第 k 个元素进行比较。
如果split小于k，则会递归调用deterministic_select(array_list, split + 1, right, k)。这将在数组的一半中寻找第 k 个元素。否则，将调用deterministic_select(array_list, left, split-1, k)函数。
总结
本章已经探讨了如何在列表中找到第 i 小的元素的方法。已经探讨了简单地对列表进行排序以执行查找第 i 小元素的操作的平凡解决方案。
还有可能不一定要在确定第 i 小的元素之前对列表进行排序。随机选择算法允许我们修改快速排序算法以确定第 i 小的元素。
为了进一步改进随机选择算法，以便我们可以获得O(n)的时间复杂度，我们着手寻找中位数的中位数，以便在分区期间找到一个良好的分割点。
从下一章开始，我们将改变重点，深入探讨 Python 的面向对象编程概念。
第十五章：面向对象设计
在软件开发中，设计通常被认为是编程之前的步骤。这并不正确；实际上，分析、编程和设计往往重叠、结合和交织。在本章中，我们将涵盖以下主题：
- 面向对象的含义
- 面向对象设计和面向对象编程之间的区别
- 面向对象设计的基本原则
- 基本的统一建模语言（UML）及其不邪恶的时候
介绍面向对象
每个人都知道什么是对象：我们可以感知、感觉和操作的有形物体。我们最早接触的对象通常是婴儿玩具。木块、塑料形状和超大拼图块是常见的第一个对象。婴儿很快学会了某些对象会做某些事情：铃响、按钮被按下，杠杆被拉动。
在软件开发中，对象的定义并没有太大的不同。软件对象可能不是可以拿起、感知或感觉的有形物体，但它们是能够做某些事情并且可以对它们做某些事情的模型。形式上，一个对象是一组数据和相关行为。
那么，知道了什么是对象，什么是面向对象呢？在词典中，oriented的意思是朝向。因此，面向对象意味着在功能上朝向建模对象。这是用于建模复杂系统的众多技术之一。它通过描述一组通过它们的数据和行为相互作用的对象来定义。
如果你读过一些炒作，你可能会遇到面向对象分析、面向对象设计、面向对象分析与设计和面向对象编程等术语。这些都是与面向对象相关的概念。
事实上，分析、设计和编程都是软件开发的各个阶段。将它们称为面向对象只是指定了正在追求的软件开发水平。
面向对象分析（OOA）是查看一个问题、系统或任务（某人想要将其转化为应用程序）并识别对象和对象之间交互的过程。分析阶段关乎于需要做什么。
分析阶段的输出是一组需求。如果我们能够在一个步骤中完成分析阶段，我们将把一个任务，比如我需要一个网站，转化为一组需求。例如，这里有一些关于网站访问者可能需要做的需求（斜体表示动作，粗体表示对象）：
- 回顾我们的历史
- 申请 工作
- 浏览、比较和订购 产品
在某种程度上，分析是一个误称。我们之前讨论的婴儿并不分析木块和拼图块。相反，她探索她的环境，操纵形状，并看看它们可能适合在哪里。一个更好的说法可能是面向对象的探索。在软件开发中，分析的初始阶段包括采访客户，研究他们的流程，并排除可能性。
面向对象设计（OOD）是将这些要求转化为实现规范的过程。设计师必须命名对象，定义行为，并正式指定哪些对象可以激活其他对象上的特定行为。设计阶段关乎于如何完成事情。
设计阶段的输出是一个实现规范。如果我们能够在一个步骤中完成设计阶段，我们将把面向对象分析期间定义的需求转化为一组类和接口，这些类和接口可以在（理想情况下）任何面向对象编程语言中实现。
面向对象编程（OOP）是将这个完全定义的设计转化为一个完全满足 CEO 最初要求的工作程序的过程。
是的，没错！如果世界符合这个理想，我们可以按照这些阶段一步一步地按照完美的顺序进行，就像所有旧教科书告诉我们的那样。通常情况下，现实世界要复杂得多。无论我们多么努力地分隔这些阶段，我们总会发现在设计时需要进一步分析的事情。当我们编程时，我们会发现设计中需要澄清的特性。
21 世纪的大部分开发都是以迭代开发模型进行的。在迭代开发中，任务的一小部分被建模、设计和编程，然后程序被审查和扩展，以改进每个功能并在一系列短期开发周期中包括新功能。
本书的其余部分是关于面向对象编程的，但在本章中，我们将在设计的背景下介绍基本的面向对象原则。这使我们能够理解这些（相当简单的）概念，而不必与软件语法或 Python 的错误信息争论。
对象和类
因此，对象是具有相关行为的数据集合。我们如何区分对象的类型？苹果和橙子都是对象，但有一个常见的谚语说它们不能相提并论。苹果和橙子在计算机编程中并不经常被建模，但让我们假设我们正在为一个水果农场做库存应用。为了便于理解，我们可以假设苹果放在桶里，橙子放在篮子里。
现在，我们有四种对象：苹果、橙子、篮子和桶。在面向对象建模中，用于表示对象类型的术语是类。因此，在技术术语中，我们现在有四个对象类。
理解对象和类之间的区别很重要。类描述对象。它们就像创建对象的蓝图。你可能在桌子上看到三个橙子。每个橙子都是一个独特的对象，但所有三个都具有与一个类相关的属性和行为：橙子的一般类。
我们库存系统中的四个对象类之间的关系可以使用统一建模语言（通常简称为UML，因为三个字母的缩写永远不会过时）类图来描述。这是我们的第一个类图：
这张图表显示橙子与篮子以某种方式相关联，而苹果也以某种方式与桶相关联。关联是两个类相关的最基本方式。
UML 在经理中非常受欢迎，有时会受到程序员的贬低。UML 图表的语法通常相当明显；当你看到一个 UML 图表时，你不必阅读教程就能（大部分）理解发生了什么。UML 也相当容易绘制，而且相当直观。毕竟，许多人在描述类及其关系时，自然会画出盒子和它们之间的线。基于这些直观图表的标准使程序员能够与设计师、经理和彼此进行轻松的沟通。
然而，一些程序员认为 UML 是浪费时间。他们引用迭代开发，他们会认为用花哨的 UML 图表制定的正式规范在实施之前就会变得多余，并且维护这些正式图表只会浪费时间，对任何人都没有好处。
这取决于所涉及的公司结构，这可能是真的，也可能不是真的。然而，每个由多个人组成的编程团队都会偶尔坐下来详细讨论他们当前正在处理的子系统的细节。在这些头脑风暴会议中，UML 非常有用，可以进行快速而轻松的沟通。即使那些嘲笑正式类图的组织也倾向于在设计会议或团队讨论中使用某种非正式版本的 UML。
此外，你将要与之交流的最重要的人是你自己。我们都认为自己能记住我们所做的设计决策，但在未来总会有*我为什么那样做？*的时刻。如果我们保存我们在开始设计时做初始图表的纸屑，最终我们会发现它们是有用的参考资料。
然而，本章并不意味着是 UML 的教程。互联网上有许多这方面的教程，以及大量关于这个主题的书籍。UML 涵盖的远不止类和对象图表；它还有用例、部署、状态变化和活动的语法。在这个面向对象设计的讨论中，我们将处理一些常见的类图表语法。你可以通过示例了解结构，并在你自己的团队或个人设计会议中下意识地选择受 UML 启发的语法。
我们的初始图表虽然是正确的，但没有提醒我们苹果是放在桶里的，或者一个苹果可以放在多少个桶里。它只告诉我们苹果与桶子有某种关联。类之间的关联通常是显而易见的，不需要进一步解释，但我们可以根据需要添加进一步的说明。
UML 的美妙之处在于大多数东西都是可选的。我们只需要在图表中指定与当前情况相符的信息。在一个快速的白板会议中，我们可能只是快速地在方框之间画线。在正式文件中，我们可能会更详细地说明。在苹果和桶子的情况下，我们可以相当有信心地说这个关联是许多苹果放在一个桶里，但为了确保没有人将其与一个苹果糟蹋一个桶混淆，我们可以增强图表如下所示：
这个图表告诉我们橙子放在篮子里，有一个小箭头显示了什么放在什么里。它还告诉我们在关联的两端可以使用的对象的数量。一个Basket可以容纳许多（用表示）Orange对象。任何一个Orange可以放在一个Basket*里。这个数字被称为对象的多重性。你可能也听说过它被描述为基数。这些实际上是稍微不同的术语。基数是指集合中实际的项目数量，而多重性指定了集合可以有多小或多大。
我有时会忘记关系线的哪一端应该有哪个多重性数字。靠近类的多重性是该类的对象可以与关联的另一端的任何一个对象相关联的数量。对于苹果放在桶子的关联，从左到右阅读，Apple类的许多实例（即许多Apple对象）可以放在任何一个Barrel中。从右到左阅读，一个Barrel可以与任何一个Apple相关联。
指定属性和行为
我们现在对一些基本的面向对象术语有了了解。对象是可以相互关联的类的实例。对象实例是具有自己一组数据和行为的特定对象；我们面前桌子上的一个特定的橙子被称为是橙子类的一个实例。这已经足够简单了，但让我们深入探讨一下这两个词的含义，数据和行为。
数据描述对象
让我们从数据开始。数据代表特定对象的个体特征。一个类可以定义所有该类对象共享的特定特征集。任何特定对象可以对给定特征具有不同的数据值。例如，我们桌子上的三个橙子（如果我们没有吃掉）可能每个重量都不同。橙子类可以有一个重量属性来表示这个数据。橙子类的所有实例都有一个重量属性，但是每个橙子对于这个属性有不同的值。属性不必是唯一的，任何两个橙子可能重量相同。作为一个更现实的例子，代表不同客户的两个对象可能对于名字属性有相同的值。
属性经常被称为成员或属性。一些作者认为这些术语有不同的含义，通常是属性是可设置的，而属性是只读的。在 Python 中，只读的概念相当无意义，所以在本书中，我们会看到这两个术语可以互换使用。此外，正如我们将在第十九章中讨论的那样，property关键字在 Python 中对于特定类型的属性有特殊的含义。
在我们的水果库存应用程序中，果农可能想要知道橙子来自哪个果园，何时采摘，以及重量是多少。他们可能还想跟踪每个篮子存放在哪里。苹果可能有颜色属性，桶可能有不同的大小。这些属性中的一些也可能属于多个类（我们可能也想知道何时采摘苹果），但是对于这个第一个例子，让我们只向我们的类图添加一些不同的属性：
根据我们的设计需要多么详细，我们还可以为每个属性指定类型。属性类型通常是大多数编程语言中标准的原始数据类型，例如整数、浮点数、字符串、字节或布尔值。然而，它们也可以表示数据结构，如列表、树或图，或者更重要的是其他类。这是设计阶段可以与编程阶段重叠的一个领域。一个编程语言中可用的各种原始数据类型或对象可能与另一个编程语言中可用的不同：
通常，在设计阶段我们不需要过于关注数据类型，因为在编程阶段会选择实现特定的细节。对于设计来说，通用名称通常足够了。如果我们的设计需要列表容器类型，Java 程序员可以选择在实现时使用LinkedList或ArrayList，而 Python 程序员（就是我们！）可能会在list内置和tuple之间进行选择。
到目前为止，在我们的水果种植示例中，我们的属性都是基本的原始数据类型。然而，有一些隐含的属性我们可以明确表示——关联。对于给定的橙子，我们可能有一个属性指向包含该橙子的篮子。
行为是动作
现在我们知道了数据是什么，最后一个未定义的术语是行为。行为是可以在对象上发生的动作。可以在特定对象类上执行的行为称为方法。在编程级别上，方法就像结构化编程中的函数，但是它们神奇地可以访问与该对象关联的所有数据。与函数一样，方法也可以接受参数并返回值。
方法的参数以对象列表的形式提供给它。在特定调用期间传递给方法的实际对象实例通常被称为参数。这些对象被方法用于执行其所需的行为或任务。返回的值是该任务的结果。
我们已经将我们比较苹果和橙子的例子扩展成了一个基本的（虽然牵强）库存应用程序。让我们再扩展一下，看看是否会出现问题。可以与橙子相关联的一个动作是采摘。如果考虑实现，采摘需要做两件事：
- 通过更新橙子的篮子属性将橙子放入篮子中
- 将橙子添加到给定篮子上的橙子列表中。
因此，采摘需要知道它正在处理的篮子是哪一个。我们通过给采摘方法一个篮子参数来实现这一点。由于我们的果农还销售果汁，我们可以在橙子类中添加一个挤方法。当调用时，挤方法可能会返回所取得的果汁量，同时将橙子从其所在的篮子中移除。
篮子类可以有一个卖的动作。当篮子被卖出时，我们的库存系统可能会更新一些尚未指定的对象的数据，用于会计和利润计算。或者，我们的橙子篮在我们卖出之前可能会变坏，所以我们添加了一个丢弃的方法。让我们把这些方法添加到我们的图表中：
向个别对象添加属性和方法使我们能够创建一个相互作用的对象系统。系统中的每个对象都是某个类的成员。这些类指定了对象可以保存的数据类型以及可以在其上调用的方法。每个对象中的数据可能与同一类的其他实例处于不同的状态；由于状态的不同，每个对象对方法调用的反应可能会有所不同。
面向对象的分析和设计主要是弄清楚这些对象是什么，以及它们应该如何相互作用。接下来的部分描述了可以用来使这些交互尽可能简单和直观的原则。
隐藏细节并创建公共接口
在面向对象设计中对对象进行建模的关键目的是确定该对象的公共接口。接口是其他对象可以访问以与该对象交互的属性和方法的集合。它们不需要，通常也不允许访问对象的内部工作。
一个常见的现实世界的例子是电视。我们与电视的接口是遥控器。遥控器上的每个按钮代表着可以在电视对象上调用的方法。当我们作为调用对象访问这些方法时，我们不知道也不关心电视是通过有线连接、卫星接收器还是互联网设备接收信号。我们不关心调整音量时发送的电子信号，或者声音是发往扬声器还是耳机。如果我们打开电视以访问内部工作，例如将输出信号分成外部扬声器和一副耳机，我们将会失去保修。
这种隐藏对象实现的过程称为信息隐藏。有时也被称为封装，但封装实际上是一个更全面的术语。封装的数据不一定是隐藏的。封装，字面上来说，是创建一个胶囊（想象一下制作一个时间胶囊）。如果你把一堆信息放进一个时间胶囊里，然后锁上并埋起来，它既被封装又被隐藏。另一方面，如果时间胶囊没有被埋起来，是解锁的或者是由透明塑料制成的，里面的物品仍然被封装，但没有信息隐藏。
封装和信息隐藏之间的区别在设计层面上基本上是无关紧要的。许多实际参考资料都将这些术语互换使用。作为 Python 程序员，我们实际上并不需要真正的信息隐藏（我们将在《Python 对象》一章中讨论这一点的原因），因此更全面的封装定义是合适的。
然而，公共接口非常重要。它需要仔细设计，因为将来很难更改它。更改接口将破坏任何正在访问它的客户对象。我们可以随意更改内部，例如使其更有效，或者在本地和网络上访问数据，客户对象仍然可以使用公共接口与之通信，而无需修改。另一方面，如果我们通过更改公开访问的属性名称或方法可以接受的参数的顺序或类型来更改接口，所有客户类也必须进行修改。在设计公共接口时，保持简单。始终根据使用的便捷性而不是编码的难度来设计对象的接口（这个建议也适用于用户界面）。
记住，程序对象可能代表真实对象，但这并不意味着它们是真实对象。它们是模型。建模的最大好处之一是能够忽略不相关的细节。我小时候制作的模型汽车外观看起来像一辆真正的 1956 年的雷鸟，但显然它不能跑。当我还太小不能开车时，这些细节过于复杂和无关紧要。这个模型是对真实概念的抽象。
抽象是与封装和信息隐藏相关的另一个面向对象的术语。抽象意味着处理最适合特定任务的细节级别。这是从内部细节中提取公共接口的过程。汽车的驾驶员需要与转向、油门和刹车进行交互。发动机、传动系统和刹车子系统的工作对驾驶员并不重要。另一方面，技工在不同的抽象级别上工作，调整发动机和排气刹车。这是汽车的两个抽象级别的例子：
现在，我们有几个指涉相似概念的新术语。让我们用几句话总结所有这些行话：抽象是使用单独的公共和私有接口封装信息的过程。私有接口可能会受到信息隐藏的影响。
从所有这些定义中得出的重要教训是使我们的模型能够被必须与其交互的其他对象理解。这意味着要特别注意细节。确保方法和属性具有合理的名称。在分析系统时，对象通常代表原始问题中的名词，而方法通常是动词。属性可能显示为形容词或更多名词。相应地为您的类、属性和方法命名。
在设计接口时，想象自己是对象，并且你非常注重隐私。除非你认为让其他对象访问关于你的数据对你最有利，否则不要让它们访问。除非你确定你希望它们能够这样做，否则不要给它们一个接口来强迫你执行特定的任务。
组合
到目前为止，我们已经学会了将系统设计为一组相互作用的对象，其中每个交互都涉及以适当的抽象级别查看对象。但我们还不知道如何创建这些抽象级别。有多种方法可以做到这一点；我们将在第二十一章中讨论一些高级设计模式，迭代器模式。但是，大多数设计模式都依赖于两个基本的面向对象原则，即组合和继承。组合更简单，所以我们从它开始。
组合是将几个对象收集在一起创建一个新对象的行为。当一个对象是另一个对象的一部分时，组合通常是一个不错的选择。我们已经在机械示例中看到了组合的第一个迹象。燃油汽车由发动机、变速器、起动机、前灯和挡风玻璃等众多部件组成。发动机又由活塞、曲轴和气门组成。在这个例子中，组合是提供抽象级别的一种好方法。汽车对象可以提供驾驶员所需的接口，同时也可以访问其组件部件，这为技师提供了更深层次的抽象，适合于诊断问题或调整发动机时进一步分解这些组件部件。
汽车是一个常见的组合示例，但在设计计算机系统时并不是特别有用。物理对象很容易分解成组件对象。人们至少自古希腊时代以来一直在做这件事，最初假设原子是物质的最小单位（当然，他们当时无法接触到粒子加速器）。计算机系统通常比物理对象更简单，但是在这种系统中识别组件对象并不会自然发生。
面向对象系统中的对象有时代表诸如人、书籍或电话等物理对象。然而更多时候，它们代表抽象的概念。人有名字，书有标题，电话用于打电话。电话、标题、账户、名字、约会和付款通常不被认为是物理世界中的对象，但它们在计算机系统中经常被建模为组件。
让我们尝试建模一个更加面向计算机的例子来看看组合是如何发挥作用的。我们将研究一个计算机化的国际象棋游戏的设计。这在 80 年代和 90 年代是学者们非常受欢迎的消遣。人们曾经预测计算机有一天会能够击败人类国际象棋大师。当这在 1997 年发生时（IBM 的深蓝击败了世界国际象棋冠军加里·卡斯帕罗夫），人们对这个问题的兴趣减弱了。如今，计算机总是赢。
作为基本的高层分析，国际象棋是由两个玩家之间进行的，使用一个包含八个 8x8 网格中的六十四个位置的棋盘的国际象棋套装。棋盘上可以有两组十六个棋子，可以以不同的方式由两个玩家交替轮流 移动。每个棋子可以吃掉其他棋子。棋盘将需要在每个回合之后在计算机屏幕上绘制自己。
我用斜体标识了描述中一些可能的对象，并使用粗体标识了一些关键方法。这是将面向对象分析转化为设计的常见第一步。在这一点上，为了强调组合，我们将专注于棋盘，而不会过多担心玩家或不同类型的棋子。
让我们从可能的最高抽象级别开始。我们有两个玩家通过轮流走棋与国际象棋棋盘交互：
这看起来不太像我们早期的类图，这是一件好事，因为它不是一个！这是一个对象图，也称为实例图。它描述了系统在特定时间点的状态，并描述了对象的特定实例，而不是类之间的交互。请记住，两个玩家都是同一个类的成员，所以类图看起来有点不同：
该图表明只有两个玩家可以与一个国际象棋棋盘交互。这也表明任何一个玩家一次只能玩一个国际象棋棋盘。
然而，我们正在讨论组合，而不是 UML，所以让我们考虑一下国际象棋棋盘由什么组成。我们暂时不关心玩家由什么组成。我们可以假设玩家有心脏和大脑等器官，但这些对我们的模型无关紧要。事实上，没有什么能阻止说的玩家本身就是深蓝，它既没有心脏也没有大脑。
然后，国际象棋棋盘由棋盘和 32 个棋子组成。棋盘又包括 64 个位置。你可以争辩说棋子不是国际象棋棋盘的一部分，因为你可以用不同的棋子替换国际象棋棋盘中的棋子。虽然在计算机版本的国际象棋中这是不太可能或不可能的，但这向我们介绍了聚合。
聚合几乎与组合完全相同。不同之处在于聚合对象可以独立存在。一个位置不可能与不同的国际象棋棋盘相关联，所以我们说棋盘由位置组成。但是，棋子可能独立于国际象棋棋盘存在，因此被称为与该棋盘处于聚合关系。
区分聚合和组合的另一种方法是考虑对象的生命周期。如果组合（外部）对象控制相关（内部）对象的创建和销毁，那么组合是最合适的。如果相关对象独立于组合对象创建，或者可以比组合对象存在更久，那么聚合关系更合理。另外，请记住，组合是聚合；聚合只是组合的一种更一般的形式。任何组合关系也是聚合关系，但反之则不然。
让我们描述我们当前的国际象棋棋盘组合，并为对象添加一些属性来保存组合关系：
组合关系在 UML 中表示为实心菱形。空心菱形代表聚合关系。你会注意到棋盘和棋子以与将它们的引用存储为国际象棋棋盘的一部分，方式完全相同。这表明，一旦再次实践中，聚合和组合之间的区别通常在设计阶段过后就不再重要。在实现时，它们的行为方式大致相同。然而，当你的团队讨论不同对象如何交互时，区分它们可能有所帮助。通常情况下，你可以将它们视为相同的东西，但当你需要区分它们时（通常是在谈论相关对象存在多长时间时），了解区别是很重要的。
继承
我们讨论了对象之间的三种关系：关联、组合和聚合。然而，我们还没有完全指定我们的国际象棋棋盘，而这些工具似乎并不能给我们提供所有我们需要的功能。我们讨论了玩家可能是人类，也可能是具有人工智能的软件。说玩家与人类关联，或者说人工智能实现是玩家对象的一部分，似乎都不太合适。我们真正需要的是能够说Deep Blue 是一个玩家，或者加里·卡斯帕罗夫是一个玩家的能力。
is a关系是由继承形成的。继承是面向对象编程中最著名、最知名和最常用的关系。继承有点像家谱。我的祖父姓菲利普斯，我父亲继承了这个姓氏。我从他那里继承了它。在面向对象编程中，一个类可以从另一个类继承属性和方法，而不是从一个人那里继承特征和行为。
例如，我们的国际象棋棋盘上有 32 个棋子，但只有六种不同类型的棋子（兵、车、象、马、国王和皇后），每种棋子在移动时的行为都不同。所有这些棋子类都有属性，比如颜色和它们所属的国际象棋棋盘，但它们在国际象棋棋盘上绘制时也有独特的形状，并且移动方式不同。让我们看看这六种类型的棋子如何从Piece类继承：
空心箭头表示各个棋子类从Piece类继承。所有子类都自动从基类继承chess_set和color属性。每个棋子提供一个不同的形状属性（在渲染棋盘时绘制在屏幕上），以及一个不同的move方法，以在每一轮中将棋子移动到棋盘上的新位置。
我们实际上知道Piece类的所有子类都需要有一个move方法；否则，当棋盘试图移动棋子时，它会感到困惑。我们可能希望创建国际象棋的一个新版本，其中有一个额外的棋子（巫师）。我们当前的设计将允许我们设计这个棋子，而不给它一个move方法。然后当棋盘要求棋子移动时，它会出错。
我们可以通过在Piece类上创建一个虚拟的移动方法来解决这个问题。然后子类可以用更具体的实现覆盖这个方法。默认实现可能会弹出一个错误消息，说该棋子无法移动。
在子类中重写方法可以开发非常强大的面向对象系统。例如，如果我们想要实现一个具有人工智能的Player类，我们可以提供一个calculate_move方法，该方法接受一个Board对象，并决定将哪个棋子移动到哪里。一个非常基本的类可能会随机选择一个棋子和方向，然后相应地移动它。然后我们可以在子类中重写这个方法，使用 Deep Blue 的实现。第一个类适合与一个新手玩；后者将挑战一个国际象棋大师。重要的是，类中的其他方法，比如通知棋盘选择了哪个移动的方法，不需要改变；这个实现可以在两个类之间共享。
在国际象棋棋子的情况下，提供移动方法的默认实现并没有太多意义。我们只需要指定移动方法在任何子类中都是必需的。这可以通过使Piece成为一个抽象类，并声明abstract的移动方法来实现。抽象方法基本上是这样说的：
我们要求这种方法存在于任何非抽象子类中，但我们拒绝在这个类中指定实现。
事实上，可能会创建一个根本不实现任何方法的类。这样的类只会告诉我们类应该做什么，但绝对不会提供如何做的建议。在面向对象的术语中，这样的类被称为接口。
继承提供了抽象
让我们来探讨面向对象术语中最长的单词。多态性是指根据实现了哪个子类来对待一个类的能力。我们已经在我们描述的棋子系统中看到了它的作用。如果我们进一步设计，我们可能会发现Board对象可以接受玩家的移动并调用棋子的move函数。棋盘不需要知道它正在处理什么类型的棋子。它只需要调用move方法，适当的子类将负责将其移动为Knight或Pawn。
多态性很酷，但在 Python 编程中很少使用这个词。Python 在允许将对象的子类视为父类的基础上又迈出了一步。在 Python 中实现的棋盘可以接受任何具有move方法的对象，无论是主教棋子、汽车还是鸭子。当调用move时，Bishop将在棋盘上对角线移动，汽车将驾驶到某个地方，而鸭子将根据心情游泳或飞行。
在 Python 中，这种多态性通常被称为鸭子类型：如果它走起来像鸭子或游泳像鸭子，那它就是鸭子。我们不在乎它是否真的是一只鸭子（是一个是继承的基石），只在乎它是游泳还是走路。雁和天鹅可能很容易提供我们所寻找的鸭子般的行为。这使得未来的设计者可以创建新类型的鸟类，而无需实际指定水鸟的继承层次结构。它还允许他们创建完全不同的插入行为，原始设计者从未计划过。例如，未来的设计者可能能够创建一个行走、游泳的企鹅，它可以使用相同的接口，而从未暗示企鹅是鸭子。
多重继承
当我们想到我们自己家族谱中的继承时，我们会发现我们不仅从一个父类那里继承特征。当陌生人告诉一个骄傲的母亲她的儿子有他父亲的眼睛时，她通常会回答类似于，是的，但他有我的鼻子。
面向对象设计也可以包括这种多重继承，它允许子类从多个父类中继承功能。在实践中，多重继承可能会很棘手，一些编程语言（最著名的是 Java）严格禁止它。然而，多重继承也有其用途。最常见的用途是创建具有两组不同行为的对象。例如，一个设计用于连接扫描仪并发送扫描文档的传真的对象可能是通过从两个独立的scanner和faxer对象继承而创建的。
只要两个类具有不同的接口，子类从它们两者继承通常不会有害。但是，如果我们从提供重叠接口的两个类继承，情况就会变得混乱。例如，如果我们有一个具有move方法的摩托车类，还有一个同样具有move方法的船类，我们想将它们合并成终极两栖车时，当我们调用move时，结果类如何知道该做什么？在设计层面上，这需要解释，在实现层面上，每种编程语言都有不同的方式来决定调用哪个父类的方法，或以什么顺序调用。
通常，处理它的最佳方式是避免它。如果你的设计出现这样的情况，你很可能做错了。退一步，重新分析系统，看看是否可以取消多重继承关系，转而使用其他关联或组合设计。
继承是扩展行为的一个非常强大的工具。它也是面向对象设计相对于早期范例的最具市场潜力的进步之一。因此，它通常是面向对象程序员首先使用的工具。然而，重要的是要认识到拥有一把锤子并不会把螺丝钉变成钉子。继承是明显的“是一个”关系的完美解决方案，但它可能会被滥用。程序员经常使用继承来在两种只有遥远关联的对象之间共享代码，而看不到“是一个”关系。虽然这不一定是一个坏设计，但这是一个很好的机会去问他们为什么决定以这种方式设计，以及是否不同的关系或设计模式更合适。
案例研究
让我们通过对一个现实世界的例子进行几次迭代的面向对象设计，将我们所有新的面向对象的知识联系在一起。我们将要建模的系统是一个图书馆目录。图书馆几个世纪以来一直在跟踪他们的库存，最初使用卡片目录，最近使用电子库存。现代图书馆有基于网络的目录，我们可以在家里查询。
让我们从分析开始。当地的图书管理员要求我们编写一个新的卡片目录程序，因为他们古老的基于 Windows XP 的程序既难看又过时。这并没有给我们太多细节，但在我们开始寻求更多信息之前，让我们考虑一下我们已经对图书馆目录了解的情况。
目录包含书籍列表。人们搜索它们以找到特定主题的书籍，特定标题的书籍，或者特定作者的书籍。书籍可以通过国际标准书号（ISBN）来唯一标识。每本书都有一个杜威十进制分类法（DDS）号码，用于帮助在特定书架上找到它。
这个简单的分析告诉我们系统中一些明显的对象。我们很快确定Book是最重要的对象，其中已经提到了几个属性，比如作者、标题、主题、ISBN 和 DDS 号码，以及作为书籍管理者的编目。
我们还注意到一些其他可能需要或不需要在系统中建模的对象。为了编目的目的，我们只需要在书上搜索作者的author_name属性。然而，作者也是对象，我们可能想要存储一些关于作者的其他数据。当我们思考这一点时，我们可能会记起一些书籍有多个作者的情况。突然间，在对象上有一个单一的author_name属性的想法似乎有点愚蠢。与每本书相关联的作者列表显然是一个更好的想法。
作者和书籍之间的关系显然是关联，因为你永远不会说“一本书是一个作者”（这不是继承），而说“一本书有一个作者”，虽然在语法上是正确的，但并不意味着作者是书籍的一部分（这不是聚合）。事实上，任何一个作者可能与多本书相关联。
我们还应该注意名词（名词总是对象的好候选者）shelf。书架是需要在编目系统中建模的对象吗？我们如何识别单独的书架？如果一本书存放在一个书架的末尾，后来因为前一个书架插入了一本新书而移到了下一个书架的开头，会发生什么？
DDS 旨在帮助在图书馆中找到实体书籍。因此，将 DDS 属性与书籍一起存储应该足以找到它，无论它存放在哪个书架上。因此，我们可以暂时将书架从我们竞争对象的列表中移除。
系统中的另一个有问题的对象是用户。我们需要了解特定用户的任何信息吗，比如他们的姓名、地址或逾期书目清单？到目前为止，图书管理员只告诉我们他们想要一个目录；他们没有提到跟踪订阅或逾期通知。在我们的脑海中，我们还注意到作者和用户都是特定类型的人；在未来可能会有一个有用的继承关系。
为了编目的目的，我们决定暂时不需要识别用户。我们可以假设用户将搜索目录，但我们不必在系统中积极对他们进行建模，只需提供一个允许他们搜索的界面即可。
我们已经确定了书上的一些属性，但目录有什么属性？任何一个图书馆有多个目录吗？我们需要对它们进行唯一标识吗？显然，目录必须有它包含的书的集合，但这个列表可能不是公共接口的一部分。
行为呢？目录显然需要一个搜索方法，可能是作者、标题和主题的分开搜索。书上有什么行为？它需要一个预览方法吗？或者预览可以通过第一页属性而不是方法来识别吗？
前面讨论中的问题都是面向对象分析阶段的一部分。但在这些问题中，我们已经确定了一些设计中的关键对象。事实上，你刚刚看到的是分析和设计之间的几个微迭代。
很可能，这些迭代都会在与图书管理员的初次会议中发生。然而，在这次会议之前，我们已经可以为我们已经明确定义的对象勾勒出一个最基本的设计，如下所示：
拿着这个基本的图表和一支铅笔，我们与图书管理员会面。他们告诉我们这是一个很好的开始，但图书馆不仅仅提供书籍；他们还有 DVD、杂志和 CD，这些都没有 ISBN 或 DDS 号码。所有这些类型的物品都可以通过 UPC 号码唯一识别。我们提醒图书管理员，他们必须在书架上找到物品，而且这些物品可能不是按 UPC 号码组织的。
图书管理员解释说每种类型都是以不同的方式组织的。CD 主要是有声书，他们只有两打库存，所以它们是按作者的姓氏组织的。DVD 根据类型划分，然后按标题进一步组织。杂志按标题组织，然后按卷和期号进一步细分。书籍，正如我们猜测的那样，是按 DDS 号码组织的。
没有以前的面向对象设计经验，我们可能会考虑将 DVD、CD、杂志和书籍分别添加到我们的目录中，并依次搜索每一个。问题是，除了某些扩展属性和识别物品的物理位置之外，这些物品的行为都大致相同。这就是继承的工作！我们迅速更新我们的 UML 图表如下：
图书管理员理解了我们勾画的图表的要点，但对locate功能有点困惑。我们使用了一个特定的用例来解释，用户正在搜索单词bunnies。用户首先向目录发送搜索请求。目录查询其内部项目列表，找到了一个标题中带有bunnies的书和一个 DVD。此时，目录并不关心它是否持有 DVD、书、CD 还是杂志；在目录看来，所有项目都是一样的。然而，用户想知道如何找到这些实体项目，因此如果目录只返回一个标题列表，那就不够完善了。因此，它调用了两个发现的项目的locate方法。书的locate方法返回一个 DDS 号码，可以用来找到放置书的书架。DVD 通过返回 DVD 的流派和标题来定位。然后用户可以访问 DVD 部分，找到包含该流派的部分，并按标题排序找到特定的 DVD。
当我们解释时，我们勾画了一个 UML序列图，解释了各种对象是如何进行通信的：
虽然类图描述了类之间的关系，序列图描述了对象之间传递的特定消息序列。从每个对象悬挂的虚线是描述对象的生命周期的生命线。每个生命线上的较宽的框表示对象中的活动处理（没有框的地方，对象基本上是空闲的，等待发生某些事情）。生命线之间的水平箭头表示特定的消息。实线箭头表示被调用的方法，而带有实心头的虚线箭头表示方法返回值。
半箭头表示发送到对象或从对象发送的异步消息。异步消息通常意味着第一个对象调用第二个对象的方法，该方法立即返回。经过一些处理后，第二个对象调用第一个对象的方法来给它一个值。这与正常的方法调用相反，正常的方法调用在方法中进行处理，并立即返回一个值。
与所有 UML 图表一样，序列图只有在需要时才能最好使用。为了画图而画图是没有意义的。但是，当您需要传达两个对象之间的一系列交互时，序列图是一个非常有用的工具。
很遗憾，到目前为止，我们的类图仍然是一种混乱的设计。我们注意到 DVD 上的演员和 CD 上的艺术家都是人的类型，但与书籍作者的处理方式不同。图书管理员还提醒我们，他们的大部分 CD 都是有声书，有作者而不是艺术家。
我们如何处理为标题做出贡献的不同类型的人？一个明显的实现是创建一个Person类，包括人的姓名和其他相关细节，然后为艺术家、作者和演员创建这个类的子类。然而，在这里真的需要继承吗？对于搜索和编目的目的，我们并不真的关心表演和写作是两种非常不同的活动。如果我们正在进行经济模拟，给予单独的演员和作者类，并不同的calculate_income和perform_job方法是有意义的，但对于编目的目的，知道这个人如何为项目做出贡献就足够了。经过深思熟虑，我们意识到所有项目都有一个或多个Contributor对象，因此我们将作者关系从书籍移动到其父类中：
Contributor/LibraryItem关系的多重性是多对多，如一个关系两端的*****字符所示。任何一个图书馆项目可能有多个贡献者（例如，DVD 上的几位演员和一位导演）。许多作者写了很多书，所以他们可以附属于多个图书馆项目。
这个小改变，虽然看起来更清洁、更简单，但丢失了一些重要的信息。我们仍然可以知道谁为特定的图书馆项目做出了贡献，但我们不知道他们是如何贡献的。他们是导演还是演员？他们是写了有声书，还是为书朗读的声音？
如果我们可以在Contributor类上添加一个contributor_type属性就好了，但是当处理多才多艺的人既写书又导演电影时，这种方法就会失效。
一个选择是向我们的LibraryItem子类中添加属性来保存我们需要的信息，比如Book上的Author，或者CD上的Artist，然后将这些属性的关系都指向Contributor类。问题在于，我们失去了很多多态的优雅。如果我们想列出项目的贡献者，我们必须寻找该项目上的特定属性，比如Authors或Actors。我们可以通过在LibraryItem类上添加一个GetContributors方法来解决这个问题，子类可以重写这个方法。然后目录永远不必知道对象正在查询的属性；我们已经抽象了公共接口：
仅仅看这个类图，就感觉我们在做错事。它又臃肿又脆弱。它可能做了我们需要的一切，但感觉很难维护或扩展。关系太多，任何一个类的修改都会影响太多的类。看起来就像意大利面和肉丸。
现在我们已经探讨了继承作为一个选项，并发现它不够理想，我们可能会回顾我们之前基于组合的图表，其中Contributor直接附属于LibraryItem。经过一些思考，我们可以看到，实际上我们只需要再添加一个关系到一个全新的类，来标识贡献者的类型。这是面向对象设计中的一个重要步骤。我们现在正在向设计中添加一个旨在支持其他对象的类，而不是对初始需求的任何部分进行建模。我们正在重构设计，以便系统中的对象，而不是现实生活中的对象。重构是程序或设计维护中的一个重要过程。重构的目标是通过移动代码、删除重复代码或复杂关系，来改进设计，以获得更简单、更优雅的设计。
这个新类由一个贡献者和一个额外的属性组成，用于标识该人对给定LibraryItem所做贡献的类型。对于特定的LibraryItem可以有许多这样的贡献，一个贡献者可以以相同的方式为不同的项目做出贡献。以下的图表很好地传达了这个设计：
首先，这种组合关系看起来不如基于继承的关系自然。然而，它的优势在于允许我们添加新类型的贡献，而不必在设计中添加一个新类。当子类有某种专业化时，继承是最有用的。专业化是在子类上创建或更改属性或行为，使其在某种程度上与父类不同。创建一堆空类仅用于识别不同类型的对象似乎有些愚蠢（这种态度在 Java 和其他一切都是对象的程序员中不太普遍，但在更务实的 Python 设计师中很常见）。如果我们看继承版本的图表，我们会看到一堆实际上什么都不做的子类：
有时候，重要的是要认识到何时不使用面向对象的原则。这个不使用继承的例子很好地提醒我们，对象只是工具，而不是规则。
练习
这是一本实用书，不是教科书。因此，我不会为你创建一堆虚假的面向对象分析问题，让你分析和设计。相反，我想给你一些可以应用到自己项目中的想法。如果你有以前的面向对象经验，你就不需要在这一章节上花太多精力。然而，如果你已经使用 Python 一段时间，但从来没有真正关心过所有的类的东西，这些都是有用的心理锻炼。
首先，想想你最近完成的一个编程项目。确定设计中最突出的对象。尽量想出这个对象的尽可能多的属性。它有以下属性吗：颜色？重量？大小？利润？成本？名称？ID 号码？价格？风格？
思考属性类型。它们是基本类型还是类？其中一些属性实际上是伪装成行为？有时，看起来像数据的东西实际上是从对象的其他数据计算出来的，你可以使用一个方法来进行这些计算。这个对象还有哪些其他方法或行为？哪些对象调用了这些方法？它们与这个对象有什么样的关系？
现在，想想即将开始的项目。项目是什么并不重要；它可能是一个有趣的业余项目，也可能是一个价值数百万美元的合同。它不必是一个完整的应用程序；它可能只是一个子系统。进行基本的面向对象分析。确定需求和相互作用的对象。勾画出一个包含该系统最高抽象级别的类图。确定主要相互作用的对象。确定次要支持对象。详细了解一些最有趣的对象的属性和方法。将不同的对象带入不同的抽象级别。寻找可以使用继承或组合的地方。寻找应该避免使用继承的地方。
目标不是设计一个系统（尽管如果你的兴趣和时间允许，你当然可以这样做）。目标是思考面向对象的设计。专注于你曾经参与过的项目，或者未来打算参与的项目，这样做就更真实了。
最后，访问你最喜欢的搜索引擎，查找一些关于 UML 的教程。有数十种教程，找一个适合你的学习方法的。为你之前确定的对象勾画一些类图或序列图。不要太过于纠结于记忆语法（毕竟，如果重要的话，你总是可以再次查阅）；只需对这种语言有所了解。你的大脑中会留下一些东西，如果你能快速勾画出下一个面向对象讨论的图表，那么交流会变得更容易一些。
总结
在本章中，我们快速浏览了面向对象范式的术语，重点放在面向对象设计上。我们可以将不同的对象分为不同的类别，并通过类接口描述这些对象的属性和行为。抽象、封装和信息隐藏是高度相关的概念。对象之间有许多不同类型的关系，包括关联、组合和继承。UML 语法对于乐趣和沟通可能会有用。
在下一章中，我们将探讨如何在 Python 中实现类和方法。
Python 入门指南（四）（4）https://developer.aliyun.com/article/1507409
