Pythonでマージソートを実装する方法は？

このブログは分割統治法に基づいています。マージソートは、問題をサブ問題に分割し、次にマージしてソリューションを征服する「分割統治」アルゴリズムです。マージソートに関するこのブログ 以下のトピックについて詳しく説明します–

• Pythonのマージソートとは何ですか？
• 分割統治法
• Pythonでのマージソートの実装
• マージソートの実装のフローチャート
• 利点と使用法

Pythonのマージソートとは何ですか？

マージソートは、分割統治アルゴリズムに基づいており、入力配列が2つに分割され、別々にソートされ、マージされてソリューションに到達します。関数merge（）は、ソートされたものをマージするために使用されます 。

分割統治法

• 配列は半分に分割され、各半分のサイズが1または0になるまで、各半分でこのプロセスが繰り返されます。
• サイズ1の配列は簡単にソートされます。
• これで、ソートされた2つの配列が1つの大きな配列に結合されます。そして、これはすべての要素が結合され、配列がソートされるまで続けられます。

これはあなたのために絵をクリアするためのマージソートの視覚化です

talendオープンスタジオチュートリアルpdf

入力配列= [3,1,4,1,5,9,2,6,5,4]

それでは、実装に移りましょう。

Pythonでのマージソートの実装

def mergeSort（nlist）：print（ 'Splitting'、nlist）if len（nlist）> 1：mid = len（nlist）// 2 lefthalf = nlist [：mid] righthalf = nlist [mid：] mergeSort（lefthalf）mergeSort （右半分）i = j = k = 0 while i
 出力： 
$ python main.py 
 （「分割」、[3、1、4、1、5、9、2、6、5、4]） 
 （「分割」、[3、1、4、1、5]） 
 （「分割」、[3、1]） 
 （「分割」、[3]） 
 （「マージ」、[3]） 
 （「分割」、[1]） 
 （「マージ」、[1]） 
 （「マージ」、[1、3]） 
 （「分割」、[4、1、5]） 
 （「分割」、[4]） 
 （「マージ」、[4]） 
 （「分割」、[1、5]） 
 （「分割」、[1]） 
 （「マージ」、[1]） 
 （「分割」、[5]） 
 （「マージ」、[5]） 
 （「マージ」、[1、5]） 
 （「マージ」、[1、4、5]） 
 （「マージ」、[1、1、3、4、5]） 
 （「分割」、[9、2、6、5、4]） 
 （「分割」、[9、2]） 
 （「分割」、[9]） 
 （「マージ」、[9]） 
 （「分割」、[2]） 
 （「マージ」、[2]） 
 （「マージ」、[2、9]） 
 （「分割」、[6、5、4]） 
 （「分割」、[6]） 
 （「マージ」、[6]） 
 （「分割」、[5、4]） 
 （「分割」、[5]） 
 （「マージ」、[5]） 
 （「分割」、[4]） 
 （「マージ」、[4]） 
 （「マージ」、[4、5]） 
 （「マージ」、[4、5、6]） 
 （「マージ」、[2、4、5、6、9]） 
 （「マージ」、[1、1、2、3、4、4、5、5、6、9]） 
 [1、1、2、3、4、4、5、5、6、9]
 
 
Javaでreplaceを使用する方法
 マージソートの実装のフローチャート 
 マージソートの利点と使用法 
他のアルゴリズムのほとんどは、ファイルやリンクリストなどのシーケンシャルデータ構造ではパフォーマンスが低下します。これらの構造では、ランダムな要素へのアクセスには、通常の一定時間ではなく、線形時間がかかります。また、マージソートの性質により、このようなデータ構造を簡単かつ迅速に処理できます。マージソートの最も優れた機能の1つは、比較の数が少ないことです。 O（n * log（n））の比較回数になりますが、クイックソートに比べて定数係数が優れているため、比較関数が遅い操作の場合に便利です。また、マージソートの分割統治アプローチにより、並列処理に便利です。
 これで、「Pythonでマージソートを実装する方法」に関するこのブログは終わりです。このコンテンツがPythonの知識に何らかの価値をもたらすことを願っています。 Pythonとそのさまざまなアプリケーションに関する詳細な知識を得るには、ライブに登録できます。  24時間年中無休のサポートと生涯アクセス。