在Python中實現/運行合併排序

我正在寫一個程序在Python中，我試圖實現合併排序算法（並使用稱爲合併來處理合並步驟），我得到一個錯誤如下。我通過L = [2,6，4,8，1]一種用於合併排序的參數：在Python中實現/運行合併排序

>>> L = [2, 6, 4, 8, 1] 
>>> mergeSort(L) 
Traceback (most recent call last): 
    File "<pyshell#1>", line 1, in <module> 
    mergeSort(L) 
    File "H:\CSIS 4014\WinPython-64bit-3.5.3.1Qt5\notebooks\sorts.py", line 19, in mergeSort 
    mergeSort(left) 
    File "H:\CSIS 4014\WinPython-64bit-3.5.3.1Qt5\notebooks\sorts.py", line 21, in mergeSort 
    merge(L, left, right, p, q, r) 
    File "H:\CSIS 4014\WinPython-64bit-3.5.3.1Qt5\notebooks\sorts.py", line 24, in merge 
    left[len(left)+1] = 999999 
IndexError: list assignment index out of range

下面是我的源代碼：

def mergeSort(L) : 
    p = 0 
    r = len(L) - 1 
    if p < r : 
     q = math.floor((p + r)/2) 
     left = L[:q] 
     right = L[q+1:] 
     mergeSort(left) 
     mergeSort(right) 
     merge(L, left, right, p, q, r) 

def merge(L, left, right, p, q, r) : 
     left[len(left)+1] = 999999 
     right[len(right)+1] = 999999 
     i = 1 
     j = 1 
     k = p 
     for k in range(r) : 
       if left[i] <= right[j] : 
         L[k] = left[i] 
         i = i + 1 
       elif L[k] == right[j] : 
         j = j + 1

我試圖使用的切片子陣列左右兩側的變量以及我的教科書中的僞代碼。我將不勝感激任何幫助！

來源

2017-09-14 Adam Day

如果'left'有5個值（'len（left）== 5'），它的索引爲'0,1,2,3,4'。嘗試索引到'len（）+ 1'將總是*超出範圍。 – TemporalWolf

left[len(left)+1] = 999999

這總是會出錯......您正在嘗試寫入不存在的元素。清單的最後一項是left[len(left) - 1]。寫入任何超出該索引的索引都是錯誤的。

也許你的意思是追加？

left.append(999999)

來源

2017-09-14 19:47:57 smarx

我仍然不確定這是如何幫助你合併排序。 – TemporalWolf

那麼爲什麼我說：左[len（left）+1] = 999999 right [len（right）+1] = 999999是因爲我想在數組的左端和右端放置哨兵。你認爲說left.append（999999）會解決這個問題嗎？ –

@TemporalWolf同意，我不確定線路的目的是什麼。 – smarx

在Python中實現/運行合併排序

回答

相關問題