Python教程-在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,...,middle] 的列表，第二个列表来自 [middle+1,?,right_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

优化

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

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

结论

归并排序是一种受欢迎且高效的算法。它对于大型列表来说是一种更有效的算法。它不依赖于导致糟糕运行时的任何不幸决策。

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

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