基本的なアイデア: マージ ソートは典型的な分割統治のアイデアであり、順序なしリストを 2 つに分割し、次に各サブシーケンスを再度 2 つに分割し、分割できなくなるまで継続します。次に、マージ プロセスが開始され、各サブシーケンスの要素を別のサブシーケンスと比較し、小さな要素を結果シーケンスに順次入れてマージし、最後にマージ ソートが完了します。
マージ操作プロセス:
そのサイズが 2 つのソートされたシーケンスの合計になるように、このスペースを使用して、2 つのソートされたシーケンスを格納します。シーケンスの開始位置 2 つのポインターが指す要素を比較し、比較的小さい要素を選択してマージ スペースに配置し、ポインターを次の位置に移動します
1 つのポインターが末尾に達するまで手順 3 を繰り返します。シーケンス
他のシーケンスの残りの要素を配置します。以下のすべての要素は、マージされたシーケンスの最後に直接コピーされます
上記のステートメントは理論的なステートメントであり、実際の例を以下で説明するために使用します:
たとえば、順序なしarray
[6,2,3,1,7]
まず、配列を次まで再帰的に分解します。
前のステップでも、実際にはこのステップと同じようにマージしましたが、それぞれのリストに番号があるため、プロセスを完全に表示することはできません。このプロセスを以下に完全に示します。 初期:[6],[2],[3],[1],[7]ステップ1、a、bから順番に数字を取り出します: 2、1、サイズを比較してcに入れ、元のリストから数字を削除すると、結果は次のようになります:
[2,6],[1,3],[7]ステップ 2、引き続き a、b から順番に数字を取り出します。つまり、上記の手順を繰り返します。今度は 2、3、大きさを比較して c に入れ、削除します。元のリストからの番号を削除すると、結果は次のようになります:
a = [2,6] b = [1,3] c = []ステップ 3、前のステップを繰り返します、結果は次のようになります:
a = [2,6] b = [3] c = [1]最後のステップ、c に 6 を追加します、結果は次のようになります:
a = [6] b = [3] c = [1,2]上記の処理を繰り返し適用することで、[1,2,3,6]と[7]のマージが達成されます最後にソート結果が得られます
a = [6] b = [] c = [1,2,3]
これこの記事には 3 つの Python 実装メソッドがリストされています:
方法 1: 上記のプロセスを翻訳したものですが、最初は少しぎこちないですa = [] b = [] c = [1,2,3,6]方法 2: 値を順番に取得するという点では、list.pop( ) メソッドを使用すると、コードがよりコンパクトで簡潔になります
[1,2,3,6,7]
方法 3: Python モジュール heapq にマージ ソート メソッドが提供されていることがわかり、このメソッドに分解結果をインポートするだけです。
#! /usr/bin/env python #coding:utf-8 def merge_sort(seq): if len(seq) ==1: return seq else: middle = len(seq)/2 left = merge_sort(seq[:middle]) right = merge_sort(seq[middle:]) i = 0 #left 计数 j = 0 #right 计数 k = 0 #总计数 while i < len(left) and j < len(right): if left[i] < right [j]: seq[k] = left[i] i +=1 k +=1 else: seq[k] = right[j] j +=1 k +=1 remain = left if i<j else right r = i if remain ==left else j while r<len(remain): seq[k] = remain[r] r +=1 k +=1 return seqPython プログラミングにおけるマージ ソート アルゴリズムの実装手順の詳細については、PHP 中国語 Web サイトに注目してください。