0

私は最近pythonを学ぶことにしました！次のコードを使用して簡単なマージソートを書きたいと思います:

def mergeSort(lst):
    l = len(lst)

    if l <= 0:
        print("empty")
        return None
    elif l == 1:
        return lst

    half = int(l / 2)
    m = lst[half]

    print(half, m)

    left = []
    right = []

    for n in lst:
        if n < m:
            left.append(n)
        else:
            right.append(n)

    left = mergeSort(left)
    right = mergeSort(right)

    return merge(left, right)

残念ながら、このコードは、[1 1 1] などのリストを処理する必要がある場合、無限ループを生成します。この間違った動作を修正する方法を提案できますか?

4

3 に答える 3

2

リストを中間点で半分に分割することになっているだけだと思います-どのアイテムが各半分に入るかを並べ替えないでください。

したがって、これの代わりに：

   left = []
   right = []
   for n in lst:
       if n < m:
           left.append(n)
       else:
           right.append(n)

これを行うだけです：

   left = lst[:half]
   right = lst[half:]
于 2013-05-18T11:21:16.227 に答える
1

あなたが実装したアルゴリズムは、あなたの場合、いわゆる「ピボット」要素を削除せずに（欠陥のある）クイックソートmです。

ピボットを正しく処理した場合、への呼び出しmergeSort(left)はすでに sorted を返すため、実行するマージ操作では、マージ ソートのようにマージを行う必要はありません。left

マージソートでは、ピボット要素はありませんm。代わりに、James が説明したように、リストを 2 つの部分に分割するだけです。

経験則として、再帰呼び出しは常に小さなデータ セットで動作する必要があります。

于 2013-05-18T11:30:07.757 に答える