我正在嘗試在 python 中實現(xiàn)合并排序，如下所示：def MergeSortTopdown(list_n): #Base condition to stop recursion if len(list_n) == 1: return list_n else: mid = int(len(list_n)/2) first_half = list_n[:mid] second_half = list_n[mid:] MergeSortTopdown(first_half) MergeSortTopdown(second_half) i = 0 j = 0 n = len(list_n) for k in range(n): if j >= len(first_half) and i < len(second_half): list_n[k] = first_half[i] i += 1 if i >= len(first_half) and j < len(second_half): list_n[k] = second_half[j] j += 1 if i < len(first_half) and j < len(second_half): if first_half[i] > second_half[j]: list_n[k] = second_half[j] j += 1 elif second_half[j] > first_half[i]: list_n[k] = first_half[i] i += 1 elif second_half[i] == first_half[j]: list_n[k] = first_half[i] if i>j: i += 1 else: j += 1 return list_n當(dāng)我用已經(jīng)排序的列表進行測試時，這似乎是合理的。但是，當(dāng)我運行時，會出現(xiàn)此錯誤：MergeSortTopdown([3,4,6,7,1,8,56,112,67])Traceback (most recent call last): File "<ipython-input-11-29db640f4fc6>", line 1, in <module> MergeSortTopdown([3,4,6,7,1,8,56,112,67]) File "C:/Users/Emmanuel Hoang/MergeSortTopDown.py", line 13, in MergeSortTopdown MergeSortTopdown(second_half) File "C:/Users/Emmanuel Hoang/MergeSortTopDown.py", line 13, in MergeSortTopdown MergeSortTopdown(second_half) File "C:/Users/Emmanuel Hoang/MergeSortTopDown.py", line 19, in MergeSortTopdown list_n[k] = first_half[i]IndexError: list index out of range你能告訴我我的代碼有什么問題嗎，有什么辦法可以改進我的代碼。先感謝您
2 回答
慕絲7291255
TA貢獻1859條經(jīng)驗 獲得超6個贊
您試圖引用列表末尾之后的元素。我print在您的代碼中添加了一些簡單的語句：
for k in range(n):
print("LOOP TOP", k, first_half, second_half, list_n)
if j >= len(first_half) and i < len(second_half):
print("TRACE", list_n, k, "\t", first_half, i)
list_n[k] = first_half[i]
i += 1
然后我將輸入列表縮短為[8,56,112,3,67].
輸出：
LOOP TOP 0 [8] [56] [8, 56]
LOOP TOP 1 [8] [56] [8, 56]
LOOP TOP 0 [3] [67] [3, 67]
LOOP TOP 1 [3] [67] [3, 67]
LOOP TOP 0 [112] [3, 67] [112, 3, 67]
LOOP TOP 1 [112] [3, 67] [3, 3, 67]
TRACE [3, 3, 67] 1 [112] 0
LOOP TOP 2 [112] [3, 67] [3, 67, 67]
TRACE [3, 67, 67] 2 [112] 1
接下來是您遇到的崩潰。first_half[1]當(dāng)只有一個元素 0 時，您嘗試獲取。
分析
您有三個連續(xù)的if語句來檢查列表邊界：
if j >= len(first_half) and i < len(second_half):
if i >= len(first_half) and j < len(second_half):
if i < len(first_half) and j < len(second_half):
你必須i和j在第一檢查切換：i是first_half下標(biāo)。此更改修復(fù)了合并：
if i < len(first_half) and j >= len(second_half):
建議
您的部分問題是您的合并邏輯過于復(fù)雜。在循環(huán)的主要部分，您有一個單一的值檢查：將較低的列表頭移動到合并的列表中。在兩個索引都在范圍內(nèi)時執(zhí)行此操作。
然后，當(dāng)一個索引到達其列表的末尾時，退出循環(huán)并添加另一個列表的剩余元素。使用extend方法。所以 ...
while i < len(first_half) and j < len(second_half):
if first_half[i] < second_half[j]:
# move smaller element to list_n;
# increment i or j as needed
k += 1
# One of these will be an empty operation.
list_n.extend(first_half[i:])
list_n.extend(second_half[j:])
POPMUISE
TA貢獻1765條經(jīng)驗 獲得超5個贊
要解決IndexError：
您在合并排序的“合并步驟”中檢查的第一種情況——如果您已經(jīng)合并了列表中的所有元素second_half——具有兩個列表的名稱first_half并second_half切換。取而代之的是：
if j >= len(first_half) and i < len(second_half):
list_n[k] = first_half[i]
i += 1
你應(yīng)該有這個：
if j >= len(second_half) and i < len(first_half):
list_n[k] = first_half[i]
i += 1
這將正確檢查上面指定的條件。
為什么會這樣：
您收到 an 的原因IndexError是因為您在嘗試調(diào)用first_half[i]之前沒有正確確認這i是列表中的有效索引first_half。
添加回答
舉報
0/150
提交
取消