Python中的合并排序|极客笔记

Python中的合并排序

合并排序与快速排序算法类似，它基于分治的概念进行工作。它是最流行和高效的排序算法之一，是分治算法类别的最佳示例。

它将给定的列表分成两半，对两半分别调用自身，然后合并两个排序好的半部分。我们定义了用于合并两个半部分的 merge() 函数。

子列表会一次又一次被分成半部分，直到每个子列表只有一个元素。然后我们将成对的一个元素列表组合成两个元素的列表，同时排序它们。排序好的两个元素对被合并成四个元素的列表，以此类推，直到获得排序好的列表。

合并排序的概念

让我们看一下下面的合并排序图表。

我们将给定的列表分成两半。如果无法均等地分割列表，也没关系。

合并排序可以使用两种方式实现 – 自上而下的方法和自下而上的方法。我们在上面的示例中使用了自上而下的方法，这是合并排序经常使用的方法。

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

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

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

首先，我们观察两个列表的第一个元素。我们发现B的第一个元素较小，所以我们将其添加到我们的排序列表中，并继续在B列表中前进。

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

现在我们看一下下一对元素2和3。2较小，所以我们将其添加到我们的排序列表中，并继续前进到下一个列表。

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

继续这个过程，我们最终得到排序好的列表{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)

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

请按以下步骤理解上述过程。

步骤1是创建列表的副本。第一个列表包含了 [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