Python 中的合併排序
Vaibhhav Khetarpal
2023年1月30日
2022年5月17日
合併排序是一種流行的排序演算法，用於對任何給定資料結構的元素進行排序。本教程討論了歸併排序演算法以及如何在 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]
歸併排序的缺點
儘管歸併排序真的很流行並且被認為是高效的，但它在各種情況下都有一些缺點，下面會提到。
- 在處理較小的資料結構集時，它可能比其他可用的排序演算法相對慢。
- 實現此演算法需要額外的記憶體空間。
- 該演算法將始終貫穿整個過程，即使給定的資料結構已經排序。
Author: Vaibhhav Khetarpal
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