Pythonソートアルゴリズムのマージソートを実装する方法

アルゴリズムの説明

このセクションの最初の高度な並べ替えアルゴリズムは、マージ ソートです。 「マージャー」という言葉には「合併する」という意味があります。名前が示すように、マージ ソート アルゴリズムは、まずシーケンスをサブシーケンスに分割し、そのサブシーケンスを並べ替えてから、順序付けられたサブシーケンスを完全な順序付けされたシーケンスにマージするアルゴリズムです。実際には分割統治の考え方が採用されています。

マージ ソートの平均時間計算量は O(nlgn)、最良の場合の時間計算量は O(nlgn)、最悪の場合の時間計算量も O(nlgn) です。その空間複雑さは O(1) です。さらに、マージ ソートは安定した並べ替えアルゴリズムです。

昇順ソートを例として、マージ アルゴリズムのプロセスを図 2-21 に示します。

元の配列は、8 つの数値の順序付けされていない配列です。 1 回の操作の後、8 つの数値の配列は 4 つの数値の 2 つの順序なし配列に分割されます。各操作では、すべての最小部分配列に要素が 1 つだけ含まれるまで、順序なし配列が半分に分割されます。配列内に要素が 1 つだけある場合は、配列を順序付けする必要があります。次に、プログラムは 2 つの小さな順序配列を 1 つの大きな順序配列にマージし始めます。まず、1 つの数値を含む 2 つの配列を 2 つの数値を含む配列にマージし、次に 2 つの数値を含む 2 つの配列を 4 つの数値を含む配列にマージし、最後に 8 つの数値を含む配列にマージします。すべての順序付けされた配列が結合されると、形成された最も長い順序付けされた配列がソートされます。

コードの実装

マージ ソート コード:

  #归并排序
nums = [5,3,6,4,1,2,8,7]
def MergeSort(num):
  if(len(num)<=1):　　　　　　　　#递归边界条件
   return num　　　　　　　　　#到达边界时返回当前的子数组
  mid = int(len(num)/2)　　　　　 #求出数组的中位数
  llist,rlist = MergeSort(num[:mid]),MergeSort(num[mid:])#调用函数分别为左右数组排序
  result = []
  i,j = 0,0
  while i < len(llist) and j < len(rlist): #while循环用于合并两个有序数组
   if rlist[j]<llist[i]:
     result.append(rlist[j])
     j += 1
   else:
     result.append(llist[i])
     i += 1
  result += llist[i:]+rlist[j:]　 #把数组未添加的部分加到结果数组末尾
  return result　　　　　　　　　#返回已排序的数组
print(MergeSort(nums))

プログラムを実行すると、出力結果は次のようになります:

[1,2,3,4,5,6,7,8]

MergeSort の場合 () 関数では、最初のステップは境界条件を判断することです。要素が 1 つだけ含まれる配列が関数のパラメーターとして渡された場合、配列内には要素のみが存在するため、配列は最小サイズに達します。配列を再帰的に分解するタスクが完了したら、分解された配列を前の再帰レベルに戻すだけです。

ソートされていない配列の長さがまだ 1 より大きい場合は、変数 Mid を使用して配列の中央の添え字を格納し、ソートされていない配列を左右の 2 つの部分配列に分割します。次に、ソートされた左右の部分配列を格納する 2 つの新しい配列を作成します。ここでは再帰の考え方が使われています。 MergeSort() 関数はリストを並べ替える関数としてのみ考えられますが、MergeSort() 関数内では関数自体を呼び出して 2 つの部分配列を並べ替えることもできます。

続いて、while ループを使用して、既にソートされた 2 つの配列をマージします。 2 つの配列内の要素の相対的なサイズを決定できないため、2 つの変数 i と j を使用して、それぞれ左側のサブ配列と右側のサブ配列で追加を待機している要素の位置をマークします。 while ループが終了すると、結果リストに追加されていない最大の要素が部分配列の最後に残っている可能性があるため、result =llist[i:] rlist[j:] ステートメントは、これらの要素が追加されないようにするためのものです。見逃されている。配列のマージが完了すると、関数は順序付けられた配列を出力します。

以上がPythonソートアルゴリズムのマージソートを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。