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 函數在簡單整數列表和自定義對象上實現了它。