在Python中實現合併排序

Question

我試圖在Python中實現簡單的合併排序算法。

TypeError: 'int' object is not subscriptable

可爲什麼我在歌廳這個錯誤任何人向我解釋：

arr=[1,3,5,2,4,6] 
n=6 
l=0 
h=n-1 

def merge_Sort(l,h): 
    if(l==h): 
     return arr[l] 

    m=(h+l)//2 
    arr1=merge_Sort(l,m) 
    arr2=merge_Sort(m+1,h) 

    s1=m-l 
    s2=h-(m+1) 
    mer=[] 
    k1=k2=0 

    while(k1<=s1 or k2<=s2): 
     if(arr1[k1] < arr2[k2]): 
      mer.append(arr1[k1]) 
      k1+=1 
     else: 
      mer.append(arr2[k2]) 
      k2+=1 

    if(k1>s1): 
     while(k2<=s2): 
      mer.append(arr2[k2]) 
      k2+=1 

    if(k2>s2): 
     while(k1<=s1): 
      mer.append(arr1[k1]) 
      k1+=1  

    return mer 

res=merge_Sort(l,h) 

print(res) 

但是運行上面的代碼，當我得到這個錯誤訊息？

Answer 1

更改此：

if(l==h): 
     return arr[l] 

到：

if(l==h): 
     return [arr[l]] 

這：

while(k1<=s1 or k2<=s2): 

到：

while(k1<=s1 and k2<=s2): 

我測試了它，它工作正常。

Answer 2

的問題在這裏：

if(l==h): 
     return arr[l] 
    ... 
    while(k1<=s1 or k2<=s2): 

使用此代碼來代替：

if(l==h): 
     return arr[l:l+1] 
    ... 
    while(k1<=s1 and k2<=s2): 

---

側面說明，這段代碼：

if(k1>s1): 
     while(k2<=s2): 
      mer.append(arr2[k2]) 
      k2+=1 

    if(k2>s2): 
     while(k1<=s1): 
      mer.append(arr1[k1]) 
      k1+=1 

可以簡化爲這個：

mer.extend(arr1[k1:s1+1]) 
    mer.extend(arr2[k2:s2+1]) 

Answer 3

TypeError: 'int' object is not subscriptable意味着你要迭代（或使用類似a[0]）在int。

在「碰撞線」之前添加此項。

print(arr1, arr2) 

輸出：1 3

所以你在做3[k2]。

Answer 4

一種替代方法將是：

DEF merge_sort的（a）：

if len(a) <= 1: 
    return a 
mid = len(a) // 2 
left = merge_sort(a[:mid]) 
right = merge_sort(a[mid:]) 
return merge(left, right) 

DEF合併（左，右）：

if not left: 
    return right 
if not right: 
    return left 
if left[0] < right[0]: 
    return [left[0]] + merge(left[1:], right) 
return [right[0]] + merge(left, right[1:])