Python 数据结构和算法实用指南（三）（3）https://developer.aliyun.com/article/1507586
选择排序算法
另一个流行的排序算法是选择排序。选择排序算法首先找到列表中最小的元素，并将其与列表中的第一个位置存储的数据交换。因此，它使子列表排序到第一个元素。接下来，识别出剩余列表中最小的元素（即剩余列表中最小的元素），并将其与列表中的第二个位置交换。这使得初始的两个元素排序。该过程重复进行，列表中剩余的最小元素应该与列表中第三个索引处的元素交换。这意味着前三个元素现在已排序。这个过程重复了(n-1)次来对n个项目进行排序。
让我们通过一个示例来理解算法的工作原理。我们将使用选择排序算法对以下 4 个元素的列表进行排序：
从索引0开始，我们搜索列表中存在于索引1和最后一个元素索引之间的最小项。找到这个元素后，将其与索引0处的数据交换。我们只需重复此过程，直到列表完全排序。
在列表中搜索最小的项目是一个递增的过程：
对元素2和5进行比较，选择2，因为它是这两个值中较小的值，因此这两个元素被交换。
交换操作后，数组如下所示：
此外，在索引0处，我们将2与65进行比较：
由于65大于2，这两个元素不会交换。在索引0处的元素2和索引3处的元素10之间进行了进一步比较。在这种情况下不会发生交换。当我们到达列表中的最后一个元素时，最小的元素将占据索引0。
在下一次迭代中，我们从索引1开始比较元素。我们重复整个过程，将索引1处存储的元素与从索引2到最后一个索引的所有元素进行比较。
第二次迭代从比较5和65开始，结果如下：
一旦我们发现5是从索引1到3的子列表中的最小值，我们将其放在索引1处。同样，从子列表2和3的索引中找到的下一个最小元素被放置在索引3处。
以下是选择排序算法的实现。函数的参数是我们想要按大小顺序排列的未排序项目列表：
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索引：
前面的图表显示了算法搜索下一个最小项的方向。
选择排序算法的最坏情况和最佳情况运行时间复杂度均为O(n2)。
快速排序算法
快速排序算法对于排序非常有效。快速排序算法属于分治类算法，类似于归并排序算法，其中我们将问题分解为更简单的小块来解决。
列表分区
快速排序的概念是对给定的列表或数组进行分区。为了对列表进行分区，我们首先选择一个枢轴。列表中的所有元素将与此枢轴进行比较。在分区过程结束时，所有小于枢轴的元素将位于枢轴的左侧，而所有大于枢轴的元素将位于数组中枢轴的右侧。
枢轴选择
为了简单起见，我们将数组中的第一个元素作为枢轴。这种枢轴选择在性能上会下降，特别是在对已排序列表进行排序时。随机选择数组中间或最后一个元素作为枢轴并不会改善快速排序的性能。我们将在下一章讨论更好的选择枢轴和找到列表中最小元素的方法。
举例说明
在这个算法中，我们将一个未排序的数组分成两个子数组，使得分区点（也称为枢轴）左侧的所有元素都应该小于枢轴，而枢轴右侧的所有元素都应该大于枢轴。在快速排序算法的第一次迭代之后，选择的枢轴点被放置在列表中的正确位置。第一次迭代之后，我们得到两个无序的子列表，并在这两个子列表上再次执行相同的过程。因此，快速排序算法将列表分成两部分，并递归地在这两个子列表上应用快速排序算法以对整个列表进行排序。
我们首先选择一个枢轴点，所有项目都将与其进行比较，并在第一次迭代结束时，该值将被放置在有序列表中的正确位置。接下来，我们使用两个指针，一个左指针和一个右指针。左指针最初指向索引1处的值，右指针指向最后一个索引处的值。快速排序算法的主要思想是移动在枢轴值错误一侧的项目。因此，我们从左指针开始，从左到右移动，直到找到一个比枢轴值大的位置。类似地，我们将右指针向左移动，直到找到一个小于枢轴值的值。接下来，我们交换左右指针指示的这两个值。我们重复相同的过程，直到两个指针交叉；换句话说，右指针索引指示的值小于左指针索引的值时。
让我们以一个数字列表{45, 23, 87, 12, 72, 4, 54, 32, 52}为例，来理解快速排序算法的工作原理。假设我们列表中的枢轴点是第一个元素45。我们从索引1处向右移动左指针，并在找到值87时停止，因为（87>45）。接下来，我们将右指针向左移动，并在找到值32时停止，因为（32<45）。
现在，我们交换这两个值，如下图所示：
之后，我们重复相同的过程，将左指针向右移动，并在找到值72时停止，因为（72>45）。接下来，我们将右指针向左移动，并在找到值4时停止，因为（4<45）。现在，我们交换这两个值，因为它们与枢轴值的方向相反。我们重复相同的过程，并在右指针索引值小于左指针索引值时停止。在这里，我们找到4作为分割点，并将其与枢轴值交换。如下图所示：
在快速排序算法的第一次迭代之后，可以观察到枢轴值45被放置在列表中的正确位置。
现在我们有了两个子列表：
- 枢轴值45左侧的子列表具有小于45的值。
- 枢轴值右侧的另一个子列表包含大于 45 的值。我们将在这两个子列表上递归应用快速排序算法，并重复此过程，直到整个列表排序完成。
实施
分区步骤对于理解快速排序算法的实现非常重要，因此我们将从实现分区开始进行检查。
让我们看另一个例子来理解实现。考虑以下整数列表。我们将使用分区函数对此列表进行分区，如下所示：
考虑以下代码：
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，标记了我们开始在数组中寻找大于主元的元素的位置，即greater_than_pivot_index = first_index + 1。右指针less_than_pivot_index变量指向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：
总之，第一次调用quick_sort函数时，它是围绕索引0的元素进行分区的。在分区函数返回后，我们得到的数组顺序为[4，3，20，43，89，77]。
正如你所看到的，主元43右边的所有元素都大于43，而左边的元素都小于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函数是一个非常简单的方法，代码不超过六行。繁重的工作由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) 时间。由于快速排序算法遵循“分而治之”的范式，它需要 O(log n) 时间；因此，快速排序算法的整体平均情况运行时间复杂度为 O(n) * O(log n) = O(n log n)。快速排序算法给出了最坏情况的运行时间复杂度为 O(n²)。快速排序算法的最坏情况复杂度是每次选择最坏的主元点，并且其中一个分区始终只有一个元素。例如，如果列表已经排序，最坏情况复杂度将发生在分区选择最小元素作为主元点时。当最坏情况复杂度发生时，可以通过使用随机化快速排序来改进快速排序算法。与其他上述排序算法相比，快速排序算法在对大量数据进行排序时非常高效。
堆排序算法
在第八章《图和其他算法》中，我们实现了一个二叉堆数据结构。我们的实现始终确保，在从堆中移除或添加元素后，使用 sink() 和 arrange() 辅助方法来维护堆顺序属性。
堆数据结构可以用来实现一种称为堆排序的排序算法。简而言之，让我们创建一个包含以下项目的简单堆：
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 次。加上 arrange() 方法，insert 操作的最坏情况运行时间为 O(n log n)，pop 方法也是如此。因此，这种排序算法的最坏情况运行时间为 O(n log n)。
不同排序算法的复杂性比较如下表所示：
| 算法 | 最坏情况 | 平均情况 | 最佳情况 |
| 冒泡排序 | O(n²) |
O(n²) |
O(n) |
| 插入排序 | O(n²) |
O(n²) |
O(n) |
| 选择排序 | O(n²) |
O(n²) |
O(n²) |
| 快速排序 | O(n²) |
O(n log n) |
O(n log n) |
| 堆排序 | O(n log n) |
O(n log n) |
O(n log n) |
总结
在本章中，我们探讨了许多重要和流行的排序算法，这些算法对许多实际应用非常有用。我们讨论了冒泡排序、插入排序、选择排序、快速排序和堆排序算法，以及它们在 Python 中的实现解释。快速排序比其他排序算法表现要好得多。在所有讨论的算法中，快速排序保留了它所排序的列表的索引。在下一章中，我们将利用这一特性来探讨选择算法。
在下一章中，我们将讨论与选择策略和算法相关的概念。
第十一章：选择算法
与在无序项目列表中查找元素相关的一组有趣的算法是选择算法。给定一个元素列表，选择算法用于从列表中找到第 i 个最小元素。在这样做的过程中，我们将回答与选择一组数字的中位数和在列表中选择第 i 个最小或最大元素有关的问题。
在本章中，我们将涵盖以下主题：
- 排序选择
- 随机选择
- 确定性选择
技术要求
本章中使用的所有源代码都在以下 GitHub 链接中提供：github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Python-Second-Edition/tree/master/Chapter11。
排序选择
列表中的项目可能会接受统计调查，比如找到平均值、中位数和众数。找到平均值和众数并不需要列表被排序。然而，要在数字列表中找到中位数，列表必须首先被排序。找到中位数需要你找到有序列表中间位置的元素。此外，当我们想要找到列表中最后最小的项目或者第一个最小的项目时，可以使用选择算法。
要在无序项目列表中找到第 i 个最小数，获取该项目出现的索引是很重要的。由于列表的元素没有排序，很难知道列表中索引为 0 的元素是否真的是第一个最小数。
处理无序列表时一个实用且明显的做法是首先对列表进行排序。在列表排序后，你可以放心地认为索引为 0 的元素将持有列表中的第一个最小元素。同样，列表中的最后一个元素将持有列表中的最后一个最小元素。然而，在长列表中应用排序算法来获取列表中的最小值或最大值并不是一个好的解决方案，因为排序是一个非常昂贵的操作。
让我们讨论一下是否可能在不排序列表的情况下找到第 i 个最小元素。
随机选择
在前一章中，我们讨论了快速排序算法。快速排序算法允许我们对无序项目列表进行排序，但在排序算法运行时保留元素索引的方法。一般来说，快速排序算法执行以下操作：
- 选择一个主元素
- 围绕主元素对未排序的列表进行分区
- 使用步骤 1和步骤 2递归地对分区列表的两半进行排序
一个有趣且重要的事实是，在每次分区步骤之后，主元素的索引不会改变，即使列表已经排序。这意味着在每次迭代后，所选的主元素值将被放置在列表中的正确位置。正是这个属性使我们能够在一个不太完全排序的列表中获得第 i 个最小数。因为随机选择是基于快速排序算法的，它通常被称为快速选择。
快速选择
快速选择算法用于获取无序项目列表中的第 k 个最小元素，并基于快速排序算法。在快速排序中，我们递归地对主元素的两个子列表进行排序。在快速排序中，每次迭代中，我们知道主元素值达到了正确的位置，两个子列表（左子列表和右子列表）的所有元素都被设置为无序。
然而，在快速选择算法中，我们递归地调用函数，专门针对具有第k小元素的子列表。在快速选择算法中，我们将枢轴点的索引与k值进行比较，以获取给定无序列表中的第k小元素。快速选择算法中将会有三种情况，它们如下：
- 如果枢轴点的索引小于
k，那么我们可以确定第k小的值将出现在枢轴点右侧的子列表中。因此，我们只需递归地调用快速选择函数来处理右子列表。 - 如果枢轴点的索引大于
k，那么很明显第k小的元素将出现在枢轴点左侧。因此，我们只需递归地在左子列表中寻找第i个元素。 - 如果枢轴点的索引等于
k，那么意味着我们已经找到了第k小的值，并将其返回。
让我们通过一个例子来理解快速选择算法的工作原理。假设有一个元素列表{45, 23, 87, 12, 72, 4, 54, 32, 52}，我们想要找出这个列表中第 3 个最小的元素——我们通过使用快速排序算法来实现这一点。
我们通过选择一个枢轴值，即 45，来开始算法。在算法的第一次迭代之后，我们将枢轴值放置在列表中的正确位置，即索引 4（索引从 0 开始）。现在，我们将枢轴值的索引（即 4）与k的值（即第 3 个位置，或索引 2）进行比较。由于这是在k<枢轴点（即 2<4），我们只考虑左子列表，并递归调用函数。
现在，我们取左子列表并选择枢轴点（即4）。运行后，4被放置在其正确的位置（即 0 索引）。由于枢轴的索引小于k的值，我们考虑右子列表。同样，我们将23作为枢轴点，它也被放置在了正确的位置。现在，当我们比较枢轴点的索引和k的值时，它们是相等的，这意味着我们已经找到了第 3 个最小的元素，并将其返回。
这个过程也在下面的图表中显示：
要实现快速选择算法，我们首先需要了解主要函数，其中有三种可能的情况。我们将算法的主要方法声明如下：
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个元素。k的值应该始终是正数；只有大于或等于零的值才被允许，这样当k为 0 时，我们知道要在列表中搜索第一个最小的项。其他人喜欢处理k参数，使其直接映射到用户正在搜索的索引，这样第一个最小的数字就映射到排序列表的0索引。
对partition函数的方法调用split = partition(array_list, left, right)，返回split索引。split数组的这个索引是无序列表中的位置，right到split-1之间的所有元素都小于split数组中包含的元素，而split+1到left之间的所有元素都大于它。
当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^(th)个元素，即使枢轴是随机选择的。
partition函数返回由less_than_pivot_index指向的枢轴索引，正如我们在前一章中看到的。
确定性选择
随机选择算法的最坏情况性能是O(n²)。可以通过改进随机选择算法的元素部分来获得O(n)的最坏情况性能。我们可以通过使用一个算法，即确定性选择，获得O(n)的性能。
中位数中位数是一种算法，它为我们提供了近似中位数值，即接近给定未排序元素列表的实际中位数的值。这个近似中位数通常用作快速选择算法中选择列表中第i^(th)最小元素的枢轴点。这是因为中位数中位数算法在线性时间内找到了估计中位数，当这个估计中位数用作快速选择算法中的枢轴点时，最坏情况下的运行时间复杂度从O(n²)大幅提高到线性的O(n)。因此，中位数中位数算法帮助快速选择算法表现得更好，因为选择了一个好的枢轴值。
确定性算法选择第i^(th)最小元素的一般方法如下：
- 选择一个枢轴：
- 将未排序项目的列表分成每组五个元素。
- 对所有组进行排序并找到中位数。
- 递归执行步骤 1和2，以获得列表的真实中位数。
- 使用真实中位数来分区未排序项目的列表。
- 递归到可能包含第
i^(th)最小元素的分区列表部分。
让我们考虑一个包含 15 个元素的示例列表，以了解确定性方法确定列表中第三个最小元素的工作原理。首先，您需要将具有 5 个元素的列表分成两个，并对子列表进行排序。一旦我们对列表进行了排序，我们就找出子列表的中位数，也就是说，元素23、52和34是这三个子列表的中位数。我们准备了所有子列表中位数的列表，然后对中位数列表进行排序。接下来，我们确定这个列表的中位数，也就是中位数的中位数，即34。这个值是整个列表的估计中位数，并用于选择整个列表的分区/枢轴点。由于枢轴值的索引为 7，大于i^(th)值，我们递归考虑左子列表。
算法的功能如下图所示：
枢轴选择
为了有效地确定列表中第 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
现在让我们了解 partition 函数的代码。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，我们将使用由 first_index 和 last_index 标记的数组部分调用 median_of_medians 函数。返回值再次存储在 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 个项目，将会有 20 个组，由 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])
创建一个空数组并将其分配给 medians，它存储分配给 sublists 的每个五个元素数组中的中位数。
for 循环遍历 sublists 中的列表列表。每个子列表都被排序，找到中位数，并存储在 medians 列表中。
medians.append(sorted(sublist)[len(sublist)//2])语句将对列表进行排序并获得存储在其中间索引的元素。这成为五个元素列表的中位数。由于列表的大小很小，使用现有的排序函数不会影响算法的性能。
从一开始我们就明白，我们不会对列表进行排序以找到第 i 个最小的元素，那么为什么要使用 Python 的 sorted 方法呢？嗯，因为我们要对一个非常小的列表进行排序，只有五个元素或更少，所以这个操作对算法的整体性能的影响被认为是可以忽略的。
此后，如果列表现在包含五个或更少的元素，我们将对 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 函数。
中位数中位数算法也可以用于选择快速排序算法中的枢轴点，从而将快速排序算法的最坏情况性能从 O(n²)显著提高到 O(n log n)的复杂度。
分区步骤
现在我们已经获得了近似中位数，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)
然后使用swap函数将unsorted_array中的第一个元素与index_of_nearest_median进行交换。
交换两个数组元素的utility函数如下所示：
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)的时间复杂度，我们着手寻找中位数中的中位数，以便在分区过程中找到一个良好的分割点。
在下一章中，我们将探讨字符串的世界。我们将学习如何高效地存储和操作大量文本。还将涵盖数据结构和常见的字符串操作。
