Pythonプログラミングにおける正規化順序付けアルゴリズムの実現ステップの詳細解

基本的な考え方：分類と順序付けは典型的な分割思想であり、一つの無秩序リストを二つに分け、各サブシーケンスをもう一つに分けて、分割ができなくなるまで続けます。その後、連結を開始するプロセスについては、各サブシーケンスと他のサブシーケンスの要素を比較し、結果系列に小さな要素を順次入れて統合し、最終的には並べ替えが完了します。
まとめて操作する過程:
結合されたシーケンスを保存するために使用される空間は、順序付けされた2つの合計の大きさにするために使用されます。
2つのポインタを設定します。最初の位置はそれぞれ2つの並べ替えられたシーケンスの開始位置です。
2つのポインタが指す要素を比較して、比較的小さい要素を結合空間に入れて、次の位置にポインタを移動します。
ステップ3を繰り返します。
他のシーケンスの残りのすべての要素を連結シーケンスの最後に直接コピーします。
上記の表現は理論的表現であり、次の例で説明します。
例えば無秩序配列

[6,2,3,1,7]

まず、この配列を再帰的に分解します。

[6],[2],[3],[1],[7]

統合の順序付けを開始するのも、再帰的な方法で行われます。
二つのマージ順序、取得:

[2,6],[1,3],[7]

前のステップでも、実はこのステップのように統合されていますが、各リストの中の一つの数によって、プロセスは完全に表示されません。以下はプロセスを完全に表示することができます。
開始:

 a = [2,6] b = [1,3] c = [] 

第1ステップは、a、bから順に数字を取り出します。2、1は大きさを比較してcに入れ、その数字を元のリストから削除します。

a = [2,6] b = [3] c = [1] 

2番目のステップは、a、bから順番に数字を取り出し、つまり上記のステップを繰り返します。今回は、2、3の大きさを比較してcに入れ、元のリストから削除します。

a = [6] b = [3] c = [1,2] 

第3ステップ、前のステップを繰り返します。結果は：

a = [6] b = [] c = [1,2,3] 

最後のステップは、6をcに追加し、結果が形成されました。

a = [] b = [] c = [1,2,3,6]

上記の流れを繰り返し適用することで、[1,2,3,6]と[7]の統合を実現します。
最終的にソート結果が得られました。

[1,2,3,6,7]

本論文は三つのpythonの実現方法を列挙した。
方法1：前に述べた過程を翻訳しました。少し不器用です。

#! /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

方法2：順番に数値を取るには、list.pop()の方法を適用して、コードがよりコンパクトで簡潔です。

#! /usr/bin/env python
#coding:utf-8


def merge_sort(lst): #         

 if len(lst) <= 1:
 return lst

 def merge(left, right):
 merged = []

 while left and right:
  merged.append(left.pop(0) if left[0] <= right[0] else right.pop(0))

 while left:
  merged.append(left.pop(0))

 while right:
  merged.append(right.pop(0))

 return merged

 middle = int(len(lst) / 2) 
 left = merge_sort(lst[:middle])
 right = merge_sort(lst[middle:])
 return merge(left, right)

方法3：元はpythonのモジュールheappqにおいて、分解後の結果をこの方法に導入すれば、規格化された順序付けの方法が提供されている。

#! /usr/bin/env python
#coding:utf-8


from heapq import merge

def merge_sort(seq):
 if len(seq) <= 1:
 return m
 else:  
 middle = len(seq)/2
 left = merge_sort(seq[:middle])
 right = merge_sort(seq[middle:])
 return list(merge(left, right))  #heapq.merge()

if __name__=="__main__":
 seq = [1,3,6,2,4]
 print merge_sort(seq)