Pythonプログラミングを使ってソートをマージする方法の紹介

この記事では主に Pythonプログラミングマージソートを実装するための具体的なコードを詳しく紹介していますので、興味のある方は参考にしてください

先週の leetcode からの質問 (Median of Two)。

Sorted Arrays) なので、マージソートの実装を詳しく見ていきたいと思います。

まずソートの考え方を説明しましょう:

まず第一に、マージソートは二分法を使用します。最終的には、そのアイデアは分割と征服です。長い

配列を取得し、それを連続的に左右の部分に分割し、それを再帰的で分割します。次に、それらを 2 つの順序付けされた配列にマージします。このままではわかりにくいかもしれないので、私が描いた絵をあげておきます。

ここではマージソートの最初のステップを示し、mid

dleに従って配列を再帰的に分割し、最後に最小サイズに分割してから2つの順序付けされた配列をソートする方法を使用します。

2つの順序付けられた

配列をソートする方法は非常に簡単です。2つの配列の最初の位置を同時に比較し、小さい方を空の配列に入れ、それを空の配列のその位置のポインタに入れます。配列を 1 つ戻してから、別の配列の前の位置との比較を続けます。最初に最後の配列がスタックからポップされると、他の配列内のすべての要素が新しい配列に追加されます。

ただし、再帰的分割の時間計算量は logN であるため、2 つの順序付けされた配列をソートする方法の計算量は N です。このアルゴリズムの時間計算量は N*logN であるため、NlogN になります。

この分析の波によれば、上の図の

行動 を見ることができます。

一番左の部分が細かく分割されると、左右に分割できなくなり、結合が始まります。

最初の組み合わせは [4, 7] のマージを完了します

2 番目の組み合わせは [4, 7, 8] のマージを完了します

3 番目の組み合わせは [3, 5] のマージを完了します

4 番目の組み合わせは完了[3, 5, 9] のマージ

5 番目の組み合わせにより、[3, 4, 5, 7, 8, 9] のマージが完了し、並べ替えが終了します。

以下にPythonコードを入れてください

def merge(a, b):
 c = []
 h = j = 0
 while j < len(a) and h < len(b):
  if a[j] < b[h]:
   c.append(a[j])
   j += 1
  else:
   c.append(b[h])
   h += 1

 if j == len(a):
  for i in b[h:]:
   c.append(i)
 else:
  for i in a[j:]:
   c.append(i)

 return c


def merge_sort(lists):
 if len(lists) <= 1:
  return lists
 middle = len(lists)/2
 left = merge_sort(lists[:middle])
 right = merge_sort(lists[middle:])
 return merge(left, right)


if name == &#39;main&#39;:
 a = [4, 7, 8, 3, 5, 9]
 print merge_sort(a)

以上がPythonプログラミングを使ってソートをマージする方法の紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。