Python 归并排序教程

数据排序是数据从业者日常工作中最常见的操作之一。许多时候，我们需要按照特定顺序显示数据以提取有意义的信息。幸运的是，现在我们不必再手动完成这项任务了。计算机可以为我们完成这项任务，并且具有无与伦比的性能。

有几种排序数据的策略。在本教程中，我们将分析其中一种最有效的排序技术。”归并排序”算法使用分而治之的策略，通过首先将未排序的数组分解为较小的数组，然后将它们按正确的顺序合并。

在接下来的部分中，我们将讨论归并排序算法的所有细节，以及它在Python中的实现方式，以及一些顺利实施的实用技巧。

什么是归并排序？

存在许多排序算法，但很难找到比归并排序性能更好的算法。毫不奇怪，这个算法被用于各种现实世界的应用，比如对大型数据库进行排序或在常规计算机上组织文件。

该算法基于分而治之的范式，可以分解为三个部分：

• 分割：这个过程将问题分解为较小的子问题。
• 征服：递归地解决这些子问题。
• 组合：将子问题的解决方案结合在一起以获得最终解决方案。

分而治之策略

让我们看看归并排序是如何工作的。假设我们想通过应用归并排序算法来对以下数字进行排序。该算法递归地将数据分成两部分，并不断分割，直到每个列表只剩一个元素。然后，我们通过将它们排序并组合成另一个列表来合并它们。

归并排序问题。来源：DataCamp

归并排序的时间和空间复杂度

在某个特定问题上，无法提前知道哪个排序算法效果最佳。除了算法外，还需要考虑几个变量，包括用于编写代码的编程语言、执行代码的硬件以及要排序数据的特性。

虽然我们无法预测排序算法的确切运行时间，但我们仍然可以通过分析时间和空间复杂度来比较各种排序算法的性能。

归并排序的时间复杂度

正如我们在关于大O表示法和时间复杂度的单独指南中所解释的那样，时间复杂度分析的目标不是预测算法的确切运行时间，而是通过分析随着输入数据量增加而变化的运行时间来评估算法的效率。

时间复杂度分析用大O表示法编写，这是一种描述函数增长或下降速度的数学表示。合并排序具有对数线性或线性对数时间复杂度，表示为O(N log(N))，其中N是列表中元素的数量。字母’O’代表’增长的阶数’。

在时间复杂度分析中，线性对数复杂度的行为几乎类似于线性复杂度，这意味着其执行时间将直接与数据量成正比。因此，如果数据量加倍，则算法处理数据所需的时间也会加倍，即分割和合并的次数会加倍。

由于合并排序的时间复杂度是线性的，因此其复杂度在最佳、平均和最坏情况下保持不变。这意味着，无论输入顺序如何，算法完成任务所需的步骤始终相同。

合并排序的空间复杂度

最后，除了完成任务所需的时间之外，分析算法复杂度时另一个重要方面是估算随着问题规模增大算法将需要多少内存来完成。

这涉及到空间复杂度和辅助空间的概念。辅助空间指算法使用的额外空间或临时空间，而空间复杂度则是指算法相对于输入大小所占用的总空间。换句话说，空间复杂度包括辅助空间和输入使用的空间。

归并排序的空间复杂度为O(N)。这是因为它使用了一个大小为N的辅助数组来合并输入数组的已排序部分。辅助数组用于存储合并的结果，而输入数组则被排序后的结果覆盖。

Python中的归并排序实现

让我们在Python中实现归并排序算法。有几种编写该算法的方法；然而，我们将坚持使用基于递归的方法，这种方法可能是最容易理解的，而且比基于迭代的其他替代方法需要的代码行数更少。

理解归并排序中的递归

如果您对这个主题还不熟悉，在编程中，递归发生在一个函数调用自身的情况下。您可以查看我们的《Python递归函数理解教程》来全面了解这些强大的函数。

要实现归并排序，首先我们定义基本情况：如果列表只有一个元素，那么它已经是有序的，我们立即返回。否则，我们将列表分成两半，left_half 和 right_half，并对它们中的每一个递归调用 merge_sort()。这个过程会持续直到所有子列表都只包含一个元素。

一旦我们有了这些有序的子列表，我们开始合并过程。为此，我们初始化三个索引变量：i 用于跟踪在 left_half 中的位置，j 用于 right_half，k 用于最终合并的列表。然后我们比较两半的元素。如果 left_half 中的当前元素较小，我们将其放入 my_list[k] 并将 i 向前移动。否则，我们取 right_half 中的元素，放入 my_list[k]，并递增 j。在每次比较后，我们将 k 向前移动到最终列表中的下一个位置。

这个过程会持续直到我们比较完一半的所有元素。如果在 left_half 或 right_half 中有任何元素剩余，我们会直接将它们附加到最终列表，确保没有数据被遗漏。由于归并排序是递归的，这个合并过程会在每个递归级别执行，直到整个列表都被排序。

Python 实现

下面，您可以找到使用上一个图表中未排序列表的代码示例：

def merge_sort(my_list):
    if len(my_list) > 1: 
        mid = len(my_list)//2
        left_half = my_list[:mid]
        right_half = my_list[mid:]
       
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
 
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                my_list[k] = left_half[i]                
                i += 1
            else:
                my_list[k] = right_half[j]
                j += 1
            k += 1
     
        while i < len(left_half):
            my_list[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            my_list[k] = right_half[j]
            j += 1
            k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)
>>> [1, 4, 20, 22, 30, 35, 40, 50, 90]

归并排序与其他排序算法

归并排序是一种相当快速的排序算法，特别适合大型数据库，通常被用作其他算法的基准。然而，当涉及到较短的列表时，它的性能往往低于其他排序算法。

在下面的表格中，您可以找到归并排序与其他流行排序算法的比较。

归并排序的实际应用

归并排序在对大型列表进行排序时具有高性能，但在处理较小列表时效率下降。同样，在输入列表已经有一定程度的顺序时，它的效率往往较低，因为归并排序无论列表的顺序如何都会执行相同的步骤。

一个归并排序特别适用的用例是链表。链表是一种数据结构，由线性连接的节点组成。每个节点包含数据以及与下一个节点连接的链接。

归并排序更适合链表，因为它只需要对数据进行顺序访问，这与链表的性质非常吻合。此外，归并排序是一种稳定的排序算法（即它在排序输出中保持相等元素的相对顺序），这在维护链表的顺序时是一个非常重要的考虑因素。

常见错误和故障排除

归并排序算法相当简单，代码改进的空间有限。然而，您可以通过考虑输入数据的大小来增加排序策略的复杂性。

我们已经确定归并排序在处理较大数据集时效果更好。对于较小的数据集，其他时间复杂度为O(N^2)的排序算法，如插入排序，可能效果更佳。在这种情况下，您只需要创建一个大小阈值，低于该阈值时选择插入排序算法而不是归并排序。

除此之外，探索并行化也是一个不错的主意。合并排序的步骤可以在合适的计算能力下轻松并行化，从而减少完成所需的时间。阅读我们的CPU与GPU指南以了解更多关于并行计算的信息。

结论

合并排序是最有效和最受欢迎的排序算法之一，但在这个美妙而不断扩展的算法宇宙中还有更多值得学习的内容。如果你对算法的技术细节、工作原理以及它们的复杂性、优点和缺点感兴趣，这些DataCamp资源可以帮助你继续学习：

• 数据结构与算法入门课程
• Python编程技能路径
• Python数据基础技能路径
• 中级Python课程
• Python数据分析师职业路径
• 大O符号和时间复杂度