Python プログラミングにおけるマージソートアルゴリズムの実装手順の詳細な紹介-Python チュートリアル-php.cn

Python プログラミングにおけるマージソートアルゴリズムの実装手順の詳細な紹介

高洛峰

リリース： 2017-03-06 13:27:37

オリジナル

1514 人が閲覧しました

基本的なアイデア: マージソートは典型的な分割統治のアイデアであり、順序なしリストを 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 seq

ログイン後にコピー

Python プログラミングにおけるマージソートアルゴリズムの実装手順の詳細については、PHP 中国語 Web サイトに注目してください。