1

コードの何が問題になっていますか? vect 値の一部のみを出力します。while ループがどこかで壊れているようです。理由がわかりません。

def print_list(vect):
    for i in range(0, len(vect)):
        print(vect[i])

def merge_sort(vect):
    left = []
    right = []    
    result = []

    for i in range(0, int(len(vect)/2)):
        left.append(vect[i])
    for i in range(int(len(vect)/2), len(vect)):
        right.append(vect[i])

    left.sort()
    right.sort()
    i = 0
    j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    print(len(result))
    return result

vect = [3, 1, 5, 7, 10, 2, 0]

vect = merge_sort(vect)
4

2 に答える 2

5

まあ、あなたの間違いは while ループの後です

while i < len(left) and j < len(right):
  ...

i < len(left)またはのいずれかである可能性があります（そしておそらくそうなるでしょう）。そのj < len(right)ため、適切な部分の接尾辞を回答に追加する必要があります。やりやすい

result += left[i:]
result += right[j:]

説明：

マージ手順を想像してみてください。最初は i と j が 0 で、ステップごとにそのうちの 1 つを前に進めます。やめる時は？それらの1つが最後に到達したとき。私が終わりに達したとしましょう。これにより、左部分全体が結果に追加されましたが、j と len(right) の間の右部分にはまだいくつかの要素があるため、それらも回答に追加する必要があります。

オフトップ:

マージソートを実装していますので、

left = merge_sort( left )
right = merge_sort( right )

それ以外の

left.sort()
right.sort()

注意:無限再帰を避けるために、マージ関数の先頭に次のチェックをコードに追加する必要があります。

if len( vect ) == 1:
   return vect

また、 print_list 関数で使用できます

print vect

または少なくとも

for x in vect
print x
于 2013-02-08T17:19:57.947 に答える
3

while ループは、左または右のいずれかが使い果たされるとすぐに終了します。これにより、使い果たされていないリストに残っているすべての要素がマージされません。

コードを次のように変更します。

def print_list(vect):
    for i in range(0, len(vect)):
        print(vect[i])

def merge_sort(vect):
    left = []
    right = []

    result = []
    for i in range(0, int(len(vect)/2)):
        left.append(vect[i])
    for i in range(int(len(vect)/2), len(vect)):
        right.append(vect[i])

    left.sort();
    right.sort();
    i = 0
    j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    if i < len(left):
        result.extend(left[i:])
    else:
        result.extend(right[j:])

    print(len(result))
    return result

vect = [3, 1, 5, 7, 10, 2, 0]

vect = merge_sort(vect)
print vect

左と右で並べ替え方法を使用している場合、リスト全体でのみ使用していない理由について少し混乱しています。しかし、あなたにはあなたの理由があると思います。:)

編集：コードブロック全体をそこに置いたので、それを見ることができます。これを実行すると、正しい [0, 1, 2, 3, 5, 7, 10] が出力されます。

于 2013-02-08T17:23:06.930 に答える