Python中的归并排序

归并排序与快速排序算法类似，都基于分治（divide and conquer）的思想。它是最流行和最高效的排序算法之一。它是分治类算法的绝佳范例。

它将给定的列表分成两个子列表，分别对这两个子列表进行递归调用，然后合并两个已排序的子列表。我们定义了用于合并两个子列表的 merge() 函数。

子列表会不断地被分成两半，直到每个子列表只包含一个元素。然后，我们将一对单元素列表合并成双元素列表，并在此过程中进行排序。排序后的双元素对会被合并成四元素列表，以此类推，直到得到排序后的列表。

归并排序概念

让我们看下面的归并排序图。

我们将给定的列表分成了两个部分。如果列表不能被平均分割，这完全没关系。

归并排序可以通过两种方式实现：自顶向下（top-down）方法和自底向上（bottom-up）方法。在上面的例子中，我们使用了自顶向下方法，这通常是归并排序最常用的方法。

自底向上方法提供了更多的优化，我们稍后将进行定义。

算法的核心部分是如何合并两个已排序的子列表。让我们来合并两个已排序的归并列表。

• A : [2, 4, 7, 8]
• B : [1, 3, 11]
• sorted : empty

首先，我们观察两个列表的第一个元素。我们发现 B 的第一个元素更小，所以我们将其添加到我们的排序列表中，并向前移动 B 列表的指针。

• A : [2, 4, 7, 8]
• B : [1, 3, 11]
• Sorted : 1

现在我们来看下一对元素 2 和 3。2 更小，所以我们将其添加到我们的排序列表中，并向前移动 A 列表的指针。

• A : [2, 4, 7, 8]
• B : [1, 3, 11]
• Sorted : 1

继续这个过程，我们最终得到一个排序列表 {1, 2, 3, 4, 7, 8, 11}。可能会出现两种特殊情况。

如果两个子列表有相同的元素 - 在这种情况下，我们可以选择其中一个子列表，并将元素添加到排序列表中。技术上讲，我们可以同时向前移动两个子列表的指针，并将元素添加到排序列表中。

当一个子列表中的元素用完时，只需要将另一个子列表中的剩余元素按顺序添加到排序列表中。

我们应该记住，我们可以按任何顺序对元素进行排序。我们这里按升序排序，但也可以轻松地按降序排序。

实施

归并排序算法是使用自顶向下方法实现的。这可能看起来有点难，所以我们将详细阐述每一步。在这里，我们将对两种类型的集合实现此算法：整数元素列表（通常用于介绍排序）和自定义对象（更实用和现实的场景）。

排序数组

算法的主要思想是将（子）列表分成两半并递归地对它们进行排序。我们继续这个过程，直到我们得到只包含一个元素的列表。让我们理解以下用于分割的函数：

我们的主要关注点是在排序发生之前将列表分成子部分。我们需要得到整数值，所以我们使用 // 运算符来获取索引。

让我们通过以下步骤来理解上述过程。

• 第一步是创建列表的副本。第一个列表包含从 [left_index,...,middle] 到 [middle+1,?,right_index] 的列表。
• 我们使用指针遍历两个列表的副本，选择两个值中较小的一个，并将它们添加到排序列表中。一旦我们将一个元素添加到列表中，我们就相应地向前移动排序列表的指针。
• 将另一个副本中剩余的元素添加到排序数组。

让我们用 Python 程序来实现归并排序。

Python 程序

输出

The given list before performing the merge sort is:
[44, 65, 2, 3, 58, 14, 57, 23, 10, 1, 7, 74, 48]
The given list after performing the merge sort is:
[1, 2, 3, 7, 10, 14, 23, 44, 48, 57, 58, 65, 74]

排序自定义对象

我们也可以使用 Python 类来排序自定义对象。此算法与上述算法几乎相同，但我们需要使其更通用，并传递比较函数。

我们将创建一个自定义类 Car，并为其添加一些字段。我们将对以下算法进行一些修改，使其更通用。我们可以通过使用 lambda 函数来实现这一点。

让我们理解下面的例子。

Python 程序

输出

Cars sorted by year:
Make: Cadillac, Model: Seville Sedan, Year: 1995
Make: Renault, Model: 33 Duster, Year: 2001
Make: Tata motor, Model: Jaguar, Year: 2004
Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015

Cars sorted by make:
Make: Cadillac, Model: Seville Sedan, Year: 1995
Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015
Make: Renualt, Model: 33 Duster, Year: 2001
Make: Tata motor, Model: Jaguar, Year: 2004

优化

我们可以改进归并排序算法的性能。首先，让我们理解自顶向下和自底向上归并排序之间的区别。自底向上方法通过迭代地对相邻列表的元素进行排序，而自顶向下方法则将列表分解为两个部分。

给定的列表是 [10, 4, 2, 12, 1, 3]，而不是将其分解为 [10], [4], [2], [12], [1], [3] - 我们将其分成可能已排序的子列表：[10, 4], [2], [1, 12], [3]，现在准备对它们进行排序。

对于较小的子列表，归并排序在时间和空间上都是效率较低的算法。因此，对于较小的子列表，插入排序比归并排序更有效。

结论

归并排序是一种流行且高效的算法。对于大型列表，它是一种更有效的算法。它不依赖于任何可能导致糟糕运行时间的糟糕决策。

归并排序有一个主要缺点。它使用额外的内存来存储合并前的列表的临时副本。然而，归并排序在软件中被广泛使用。它的性能很快，并且能产生出色的结果。

我们简要讨论了归并排序的概念，并通过 lambda 函数（用于比较）在简单整数列表和自定义对象上进行了实现。