Python 中的归并排序

归并排序类似于快速排序算法，因为它基于分治的概念。它是最流行和最有效的排序算法之一。这是分而治之类算法的最好例子。

它将给定的列表分成两半，调用自己的两半，然后合并两个已排序的一半。我们定义 merge() 函数用于合并两个半体。

子列表被一次又一次地分成两半，直到我们每个都只得到一个元素。然后，我们将一对元素列表组合成两个元素列表，在这个过程中排序它们。排序后的两个元素对被合并到四个元素列表中，以此类推，直到我们得到排序后的列表。

归并排序概念

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

我们已经把给定的清单分成两半。这个列表不能被分成相等的部分，这一点都不重要。

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

自下而上的方法提供了更多的优化，我们将在后面定义。

算法的主要部分是我们如何组合两个排序的子列表。让我们合并两个排序的合并列表。

• A : [ 2 ，4，7，8]
• B : [ 1 ，3，11]
• 已排序:空

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

• A : [ 2 ，4，7，8]
• B : [1， 3 ，11]
• 已排序:1

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

• A : [ 2 ，4，7，8]
• B : [1， 3 ，11]
• 已排序:1

继续这个过程，我们最终得到{1，2，3，4，7，8，11}的排序列表。可以有两种特殊情况。

• 如果两个子列表都有相同的元素怎么办——在这种情况下，我们可以移动其中一个子列表，并将元素添加到排序列表中。从技术上讲，我们可以在两个子列表中前进，并将元素添加到排序列表中。
• 我们在一个子列表中没有剩余的元素。当我们用完子列表中的时，只需一个接一个地添加第二个的元素。

我们应该记住，我们可以按照任何顺序排序元素。我们按升序排序给定的列表，但我们可以很容易地按降序进行排序。

履行

归并排序算法通过使用自顶向下的方法来实现。看起来可能有点困难，所以我们将详细阐述每一步。在这里，我们将在两种类型的集合上实现这个算法——整数元素的列表(通常用于引入排序)和一个自定义对象(一个更实际和现实的场景)。

排序数组

算法的主要概念是将(子)列表分成两半并递归排序。我们继续这个过程，直到我们得到只有一个元素的列表。让我们理解除法的以下功能-

def merge_sort(array, left_index, right_index): 
       if left_index >= right_index: 
                 return middle = (left_index + right_index)//2 
       merge_sort(array, left_index, middle) 
       merge_sort(array, middle + 1, right_index) 
       merge(array, left_index, right_index, middle) 

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

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

• 第一步是创建列表的副本。第一个列表包含从【left _ index，...，中] 和第二个来自【中+1，？，右 _index] 。
• 我们使用指针遍历列表的两个副本，选择两个值中较小的值，并将它们添加到排序列表中。一旦我们将元素添加到列表中，无论如何我们都会在排序列表中前进。
• 将另一个副本中的剩余元素添加到已排序的数组中。

让我们在 Python 程序中实现归并排序。

Python 程序

# funtion to divide the lists in the two sublists
def merge_sort(list1, left_index, right_index):
    if left_index >= right_index:
        return

    middle = (left_index + right_index)//2
    merge_sort(list1, left_index, middle)
    merge_sort(list1, middle + 1, right_index)
    merge(list1, left_index, right_index, middle)

    # Defining a function for merge the list
def merge(list1, left_index, right_index, middle):

   # Creating subparts of a lists
    left_sublist = list1[left_index:middle + 1]
    right_sublist = list1[middle+1:right_index+1]

    # Initial values for variables that we use to keep
    # track of where we are in each list1
    left_sublist_index = 0
    right_sublist_index = 0
    sorted_index = left_index

    # traverse both copies until we get run out one element
    while left_sublist_index < len(left_sublist) and right_sublist_index < len(right_sublist):

        # If our left_sublist has the smaller element, put it in the sorted
        # part and then move forward in left_sublist (by increasing the pointer)
        if left_sublist[left_sublist_index] <= right_sublist[right_sublist_index]:
            list1[sorted_index] = left_sublist[left_sublist_index]
            left_sublist_index = left_sublist_index + 1
        # Otherwise add it into the right sublist
        else:
            list1[sorted_index] = right_sublist[right_sublist_index]
            right_sublist_index = right_sublist_index + 1

        # move forward in the sorted part
        sorted_index = sorted_index + 1

    # we will go through the remaining elements and add them
    while left_sublist_index < len(left_sublist):
        list1[sorted_index] = left_sublist[left_sublist_index]
        left_sublist_index = left_sublist_index + 1
        sorted_index = sorted_index + 1

    while right_sublist_index < len(right_sublist):
        list1[sorted_index] = right_sublist[right_sublist_index]
        right_sublist_index = right_sublist_index + 1
        sorted_index = sorted_index + 1

list1 = [44, 65, 2, 3, 58, 14, 57, 23, 10, 1, 7, 74, 48]
merge_sort(list1, 0, len(list1) -1)
print(list1)

输出:

[1, 2, 3, 7, 10, 14, 23, 44, 48, 57, 58, 65, 74]

对自定义对象排序

我们也可以使用 Python 类排序自定义对象。这个算法几乎和上面的相似，但是我们需要使它更加通用，并通过比较函数。

我们将创建一个自定义类 Car，并向其中添加一些字段。我们对下面的算法做了一些修改，使其更加通用。我们可以通过使用 lambda 函数来做到这一点。

让我们理解下面的例子。

Python 程序

class Car:
    def __init__(self, make, model, year):
        self.make = make
        self.model = model
        self.year = year

    def __str__(self):
        return str.format("Make: {}, Model: {}, Year: {}", self.make, self.model, self.year)

def merge(list1, l, r, m, comp_fun):
    left_copy = list1[l:m + 1]
    r_sublist = list1[m+1:r+1]

    left_copy_index = 0
    r_sublist_index = 0
    sorted_index = l

    while left_copy_index < len(left_copy) and r_sublist_index < len(r_sublist):

        # We use the comp_fun instead of a simple comparison operator
        if comp_fun(left_copy[left_copy_index], r_sublist[r_sublist_index]):
            list1[sorted_index] = left_copy[left_copy_index]
            left_copy_index = left_copy_index + 1
        else:
            list1[sorted_index] = r_sublist[r_sublist_index]
            r_sublist_index = r_sublist_index + 1

        sorted_index = sorted_index + 1

    while left_copy_index < len(left_copy):
        list1[sorted_index] = left_copy[left_copy_index]
        left_copy_index = left_copy_index + 1
        sorted_index = sorted_index + 1

    while r_sublist_index < len(r_sublist):
        list1[sorted_index] = r_sublist[r_sublist_index]
        r_sublist_index = r_sublist_index + 1
        sorted_index = sorted_index + 1

def merge_sort(list1, l, r, comp_fun):
    if l >= r:
        return

    m = (l + r)//2
    merge_sort(list1, l, m, comp_fun)
    merge_sort(list1, m + 1, r, comp_fun)
    merge(list1, l, r, m, comp_fun)

car1 = Car("Renault", "33 Duster", 2001)
car2 = Car("Maruti", "Maruti Suzuki Dzire", 2015)
car3 = Car("Tata motor", "Jaguar", 2004)
car4 = Car("Cadillac", "Seville Sedan", 1995)

list1 = [car1, car2, car3, car4]

merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.year < carB.year)

print("Cars sorted by year:")
for car in list1:
    print(car)

print()
merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.make < carB.make)
print("Cars sorted by make:")
for car in list1:
    print(car)

输出:

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 函数在简单整数列表和自定义对象上实现了它。