Python 中的合併排序

Vaibhhav Khetarpal 2023年1月30日
  1. 在 Python 中使用遞迴實現歸併排序
  2. 在 Python 中使用迭代合併排序
Python 中的合併排序

合併排序是一種流行的排序演算法,用於對任何給定資料結構的元素進行排序。本教程討論了歸併排序演算法以及如何在 Python 中實現它。

合併排序是分治法的一個主要例子,用於對大型資料集進行排序。該演算法首先將給定的資料結構分成兩部分,然後在兩半上重複相同的過程。最後,它將兩半重新組合在一起以有效地獲得排序值。因此,我們稱其為分而治之方法的主要例子。

這個演算法最好的部分是它在所有三種可能的情況下(平均情況、最佳情況和最壞情況)都具有一致的時間複雜度 O(nlogn)。由於這個事實,它通常被認為是有效的,並且是大型資料集的首選。

我們現在將看到如何使用 Python 程式語言實現歸併排序演算法。

在 Python 中使用遞迴實現歸併排序

歸併排序是在 Python 中藉助遞迴函式簡單實現的。

以下程式碼使用遞迴在 Python 中實現歸併排序。

def m(left, right):
    if not len(left) or not len(right):
        return left or right

    result = []
    i, j = 0, 0
    while len(result) < len(left) + len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
        if i == len(left) or j == len(right):
            result.extend(left[i:] or right[j:])
            break

    return result


def msort(list):
    if len(list) < 2:
        return list

    middle = int(len(list) / 2)
    left = msort(list[:middle])
    right = msort(list[middle:])

    return m(left, right)


lst = [5, 9, 3, 7, 15, 6]
print("Given List:")
print(lst)
print("\n")
print("Sorted List:")
print(msort(lst))

上面的程式碼提供了以下輸出:

Given List:
[5, 9, 3, 7, 15, 6]
Sorted List:
[3, 5, 6, 7, 9, 15]

程式碼說明:

  • 只要沒有獲得兩個相鄰的值,在每次遞迴呼叫中,給定的列表都會分成兩半,
  • 建立並使用 m() 函式來合併最初在第一步中劃分的兩半。
  • msort() 函式執行程式中給定列表的大部分劃分和排序部分。

在 Python 中使用迭代合併排序

迭代歸併排序演算法與一般的遞迴方法略有不同,前者使用自下而上的方法,而後者使用自上而下的方法。但是,兩種方法的時間複雜度和最終答案完全相同。

此外,遞迴歸併排序方法使用顯式輔助堆疊,而在迭代歸併排序演算法實現中則不需要它。

以下程式碼使用迭代歸併排序演算法在 Python 中實現歸併排序。

def msort(a):
    width = 1
    n = len(a)
    while width < n:
        l = 0
        while l < n:
            r = min(l + (width * 2 - 1), n - 1)
            m = (l + r) // 2
            if width > n // 2:
                m = r - (n % width)
            mer(a, l, m, r)
            l += width * 2
        width *= 2
    return a


def mer(a, l, m, r):
    n1 = m - l + 1
    n2 = r - m
    L = [0] * n1
    R = [0] * n2
    for i in range(0, n1):
        L[i] = a[l + i]
    for i in range(0, n2):
        R[i] = a[m + i + 1]

    i, j, k = 0, 0, l
    while i < n1 and j < n2:
        if L[i] > R[j]:
            a[k] = R[j]
            j += 1
        else:
            a[k] = L[i]
            i += 1
        k += 1

    while i < n1:
        a[k] = L[i]
        i += 1
        k += 1

    while j < n2:
        a[k] = R[j]
        j += 1
        k += 1


a = [5, 9, 3, 7, 15, 6]
print("Given List:")
print(a)
msort(a)
print("Sorted List:")
print(a)

上面的程式碼提供了以下輸出:

Given List:
[5, 9, 3, 7, 15, 6]
Sorted List:
[3, 5, 6, 7, 9, 15]

歸併排序的缺點

儘管歸併排序真的很流行並且被認為是高效的,但它在各種情況下都有一些缺點,下面會提到。

  • 在處理較小的資料結構集時,它可能比其他可用的排序演算法相對慢。
  • 實現此演算法需要額外的記憶體空間。
  • 該演算法將始終貫穿整個過程,即使給定的資料結構已經排序。
Vaibhhav Khetarpal avatar Vaibhhav Khetarpal avatar

Vaibhhav is an IT professional who has a strong-hold in Python programming and various projects under his belt. He has an eagerness to discover new things and is a quick learner.

LinkedIn

相關文章 - Python Sorting