我需要將偽代碼轉換為反映該偽代碼的合并排序演算法。我是偽代碼的新手，所以我遇到了麻煩。誰能告訴我我的演算法有什么問題？請注意，偽代碼中的陣列是 1 索引的。
偽代碼：
MergeSort(A[1 .. n]):
if n > 1
m ← bn/2c
MergeSort(A[1 .. m])
MergeSort(A[m 1 .. n])
Merge(A[1 .. n], m)
Merge(A[1 .. n], m):
i ← 1; j ← m 1
for k ← 1 to n
if j > n
B[k] ← A[i]; i ← i 1
else if i > m
B[k] ← A[ j]; j ← j 1
else if A[i] < A[ j]
B[k] ← A[i]; i ← i 1
else
B[k] ← A[ j]; j ← j 1
for k ← 1 to n
A[k] ← B[k]
我的代碼
def mergeSort(arr):
n = len(arr)
if n > 1:
m = n//2
mergeSort(arr[:m])
mergeSort(arr[m:])
merge(arr, m)
def merge(arr, m):
n = len(arr)
i = 0
j = m
b = [0] * n
for k in range(n):
if j >= n:
b[k] = arr[i]
i = 1
elif i > m-1:
b[k] = arr[j]
j = 1
elif arr[i] < arr[j]:
b[k] = arr[i]
i = 1
else:
b[k] = arr[j]
j = 1
for k in range(n):
arr[k] = b[k]
uj5u.com熱心網友回復：
問題是在偽代碼版本中，符號 A[1..m] 應該表示陣列的一個磁區，但是就地，而不是作為一個新陣列（切片）：它就像一個視窗陣列的一部分，有自己的索引，但不復制。
Python 中串列切片的翻譯并未反映這一點。arr[:m]創建一個新串列，因此無論mergeSort(arr[:m])對該新串列做什么，它都不會觸及arr自身：所有這些作業都是徒勞的，因為它不會 mutate arr，而是它的切片副本，我們無法訪問它。
一種解決方案是不創建切片，而是將預期磁區的開始/結束索引傳遞給函式呼叫。
這是改編后的代碼：
def mergeSort(arr):
mergeSortRec(arr, 0, len(arr))
def mergeSortRec(arr, start, end):
n = end - start
if n > 1:
m = start n//2
mergeSortRec(arr, start, m)
mergeSortRec(arr, m, end)
merge(arr, start, m, end)
def merge(arr, start, m, end):
n = end - start
i = start
j = m
b = [0] * n
for k in range(n):
if j >= end:
b[k] = arr[i]
i = 1
elif i >= m:
b[k] = arr[j]
j = 1
elif arr[i] < arr[j]:
b[k] = arr[i]
i = 1
else:
b[k] = arr[j]
j = 1
for k in range(n):
arr[start k] = b[k]
uj5u.com熱心網友回復：
這段代碼對我來說作業得很好，但是你的操作正在被應用，所以你只需要呼叫帶有陣列的函式來排序而不是獲取回傳值（它總是無，因為你在功能mergeSort）
arr = np.random.uniform(1, 10, 10)
print(arr)
[2.10748505 9.47408117 5.4620788 1.5585025 9.57387679 4.13719947
1.28671255 4.150946 2.84044402 6.56294717]
mergeSort(arr)
print(arr)
[1.28671255 1.5585025 2.10748505 2.84044402 4.13719947 4.150946
5.4620788 6.56294717 9.47408117 9.57387679]
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/508720.html