要將兩個已排序的數列M和N合併成一個新的已排序數列P，並使合併後的數列依小到大排序，可以使用合併排序（Merge Sort）中的合併（Merge）步驟。該步驟的執行時間為O(m + n)，是最佳的時間複雜度。
python
def sort(M, N, m, n):
# 創建一個新的列表P來存放合併後的結果
P = [0] * (m + n)
i = 0 # M的指標
j = 0 # N的指標
k = 0 # P的指標
# 合併兩個已排序數列
while i < m and j < n:
if M[i] <= N[j]:
P[k] = M[i]
i += 1
else:
P[k] = N[j]
j += 1
k += 1
# 將M中剩餘的元素加入P
while i < m:
P[k] = M[i]
i += 1
k += 1
# 將N中剩餘的元素加入P
while j < n:
P[k] = N[j]
j += 1
k += 1
return P
# 範例使用
M = [1, 3, 5, 7]
N = [2, 4, 6, 8]
m = len(M)
n = len(N)
P = sort(M, N, m, n)
print("合併後的數列P：", P)
演算法說明
初始設置：創建一個大小為 m + n 的新陣列 P 來存放合併後的結果，並初始化指標 i、j 和 k 分別指向 M、N 和 P 的起始位置。
合併步驟：在 M 和 N 中進行比較，將較小的元素放入 P 中，然後移動對應的指標。重複此步驟直到其中一個數列到達末尾。
處理剩餘元素：將 M 或 N 中剩餘的元素依次放入 P 中。
返回結果：返回合併後的已排序數列 P。
時間複雜度
該演算法的時間複雜度為O(m + n)，這是因為每個元素最多被處理一次，因此該算法是最佳的合併排序方法。
阿摩線上測驗
登入