2

私はPythonが初めてで、Pythonでmerge_sortを実装しようとしています。これが私のコードです。しかし無限ループに陥ります。誰でも理由を指摘できますか？ありがとう

def merge_sort(a):
    '''implement merge sort for array'''
    l = len(a)
    if l == 1:
        return a[0]
    a1 = merge_sort(a[:l/2-1])
    a2 = merge_sort(a[l/2:-1])
    a_sort = []
    idx1, idx2 = 0, 0
    #for i in range(l):
    if idx1 == len(a1):
        a_sort.append(a2[idx2:])
        import ipdb; ipdb.set_trace()
        return a_sort
    elif idx2 == len(a2):
        a_sort.append(a1[idx1:])
        return a_sort
    else:      
        if a1[idx1] >= a2[idx2]:
            a_sort.append(a2[idx2])
            idx2 += 1
        else:
            a_sort.append(a1[idx1])
            idx1 += 1
4

3 に答える 3

0

問題は、再帰が空のリスト (つまり) になると、何かを返す前に 2 回l == 0呼び出すことです。merge_sort([])というチェックを追加する必要がありますif l == 0: return []。

また、あなたのチェックif l == 1: return a[0]は少し間違っています。merge_sort常にリストを返す必要がありますが、これはリスト要素 (数値または文字列など) を返します。だから、それはおそらくちょうどあるはずです

if l <= 1:
    return a

さらに、a2実際には配列の最後の要素が含まれていませa[l/2:]んa[l/2:-1]。(Python の範囲には最後の要素が含まれないことに注意してください。)

これはコードの正確性には影響しませんが、l // 2整数除算を意味するために使用する必要があります。Python3 で、またはそうする場合from __future__ import division、が奇数l/2の場合は float になります。l

于 2012-04-15T06:37:28.980 に答える
0

Dougal と Andrei が指摘したように、無限ループはチェックされていないエッジ条件によって引き起こされます。if l == 1:行をw/に置き換えif l < 2:ます。
コードには他にも問題があります。

  • a位置によるリストの左部分と右部分は、とl/2に対応a[:l/2]してa[l/2:]います。マイナス 1 する必要はありません。位置が 2 つのアイテムの間にあると考えてください。
  • およびブランチの.extend()代わりに使用append()ifelif
  • コメントアウトされた forloop を元に戻すことを忘れないでください。
  • returnとうとう無い

そして通常、while構造体の方が便利です

while idx1 < len(a1) and idx2 < len(a2):
    'code in your else branch'    
if idx1 < len(a1):
    a_sort.extend(a1[idx1:])
else:
    a_sort.extend(a2[idx2:])
return a_sort
于 2012-04-15T07:37:06.013 に答える
0

ありがとう！以下の作業コード

def merge_sort(a):
'''implement merge sort for array'''
l = len(a)
if l == 1:
    return a
a1 = merge_sort(a[:l//2])
a2 = merge_sort(a[l//2:])
a_sort = []
idx1, idx2 = 0, 0
while idx1 < len(a1) and idx2 < len(a2):
    if a1[idx1] >= a2[idx2]:
        a_sort.append(a2[idx2])
        idx2 += 1
    else:
        a_sort.append(a1[idx1])
        idx1 += 1
if idx1 < len(a1):
    a_sort.extend(a1[idx1:])
else:
    a_sort.extend(a2[idx2:])
return a_sort
于 2012-04-15T17:04:47.580 に答える