Javaでマージソートアルゴリズムを実装する方法例を詳しく解説

この記事では、Java のマージ ソート アルゴリズムの詳細な説明に関する関連情報を主に紹介します。マージ ソート アルゴリズムは、時間計算量が O(N logN) であるため、ソート アルゴリズムとも呼ばれます。日常生活や仕事で非常に重要であり、必要な場合は Java 要素のマージ ソート アルゴリズムの詳細な説明を参照してください。各要素は 1 つの要素であり、隣接する 2 つの要素は小さいものから順にソートされます。各全体には 1 つまたは 2 つの要素が含まれており、各全体が並べ替えられるため、全体が「マージ」され続けるため、特定のアルゴリズムを使用できます。それらをマージすると、各全体には 3 ～ 4 つの要素が含まれ、すべての全体が 1 つの全体にマージされ、最終的な全体は元の配列をソートした結果になります。 ️ 2 つの全体の最小要素 (実際に昇順に並べ替えられていると仮定して) が毎回取得され、新しい配列に入れられ、順番に循環されます。最終的に、2 つの全体の要素はすべて After になります。取得すると、全体が昇順にソートされます。結合プロセスは、(図に示すように) 2 つの昇順のデッキ A と B を持つようなもので、毎回 1 つの要素が上から取り出され、デッキ C に配置されます:

、隣接する 2 つの整数 A と B について、その中の要素が昇順にソートされ、一時的な配列 C があり、次に A と B の先頭の 2 つの要素が比較され、小さい方の要素が取り出されます。取り出された要素全体について、その要素を指す添え字が 1 つ下に移動され、続けて 2 つの全体のうち小さい方の先頭の要素が C に入れられ、一定のときにループされます。要素全体がフェッチされ、他の全体のすべての要素を C に直接移動します。 C 全体の場合、A と B をソートすることで得られます。A と B は隣接する 2 つの全体であるため、最終的に必要なのは、C の要素を A と B で構成される共通の全体にコピーすることだけです。これにより、A と B をマージし、同時に並べ替えるという目的も達成されます。以下はマージとソートの具体的なアルゴリズムです:

public class MergeSort {
 public static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] arr) {
  AnyType[] tmp = ((AnyType[]) new Comparable[arr.length]);
  mergeSort(arr, 0, arr.length - 1, tmp);
 }

 private static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] arr, int start, int end, AnyType[] tmp) {
  if (start < end) {
   int mid = (start + end) >> 1;
   mergeSort(arr, start, mid, tmp);
   mergeSort(arr, mid + 1, end, tmp);
   merge(arr, start, mid, end, tmp);
  }
 }

 private static <AnyType extends Comparable<? super AnyType>> void merge(AnyType[] arr, int start, int mid, int end, AnyType[] tmp) {
  int i = start, j = mid + 1, k = start;
  while (i <= mid && j <= end) {
   if (arr[i].compareTo(arr[j]) < 0) {
    tmp[k++] = arr[i++];
   } else {
    tmp[k++] = arr[j++];
   }
  }

  while (i <= mid) {
   tmp[k++] = arr[i++];
  }

  while (j <= end) {
   tmp[k++] = arr[j++];
  }

  for (int m = start; m <= end; m++) {
   arr[m] = tmp[m];
  }
 }
}

コードには 2 つの主要なメソッドがあります。最初のメソッドは再帰的メソッドです。このメソッドの関数の定義を明確にしてください。ここでのこの再帰メソッドの目的は、受信配列の先頭と末尾の間で要素を並べ替えることであり、 tmp は補助配列です。このメソッドの具体的な実装では、最初に再帰を呼び出して start とmid の間で要素を並べ替え、次に再帰を呼び出して Mid と end の間で要素を並べ替えるというアイデアがわかります。 from startからmidとfrommidからendがソートされており、この時点で2番目のメソッドを呼び出す必要があります。

2 番目のメソッドの機能は、2 つのソートされた部分をマージすることです

最初のメソッドの場合、最後のステップは 2 番目のメソッドを実行し、このメソッドの前の 2 つのステップでソートされた部分をマージします。 。 2 番目の方法については、実装の考え方は前述と同じです。2 つのカードの山から小さい要素を取り出し、それを一時配列に置きます。1 つのカードの山が取り出されたら、残りの要素を置きます。 2 番目のデッキでは、最後に一時配列の要素を元の配列に戻します。

この記事では主にマージソートの考え方を詳しく説明し、具体的なコードや考え方に基づいてコードを分析します。

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