Java-Datenstruktur-Sortieralgorithmus (2) Zusammenführungssortierung

In diesem Artikel wird hauptsächlich der Merge-Sortierungsalgorithmus für Java-Datenstrukturen vorgestellt. Er analysiert detailliert die Prinzipien, Implementierungstechniken und zugehörigen Vorsichtsmaßnahmen anhand konkreter Beispiele.

Das Beispiel beschreibt den Merge-Sort des Java-Datenstruktur-Sortieralgorithmus. Geben Sie es als Referenz an alle weiter. Die Einzelheiten lauten wie folgt:

Die oben erwähnten Sortierarten ordnen eine Gruppe von Datensätzen entsprechend der Größe der Schlüsselwörter und der Idee von in einer geordneten Reihenfolge an Zusammenführungssortierung ist: Basierend auf Zusammenführen zwei oder mehr geordnete Listen zu einer neuen geordneten Liste zusammenführen

Sortieralgorithmus zusammenführen: Angenommen, die Anfangssequenz enthält n Datensätze. Behandeln Sie diese n Datensätze zunächst als n geordnete Teilsequenzen, jede Teilsequenz hat eine Länge von 1, und führen Sie sie dann paarweise zusammen, um n/2 Längen von 2 zu erhalten (wenn n eine ungerade Zahl ist, beträgt die Länge der letzten Sequenz 1). geordnete Teilfolge. Auf dieser Basis werden die geordneten Teilfolgen der Länge 2 übersichtlich zusammengeführt, um mehrere geordnete Teilfolgen der Länge 4 zu erhalten. Wiederholen Sie dies, bis eine geordnete Folge der Länge n erhalten wird. Diese Methode heißt: 2-Wege-Zusammenführungssortierung (die Grundoperation besteht darin, zwei benachbarte geordnete Teilsequenzen in der zu sortierenden Sequenz zu einer geordneten Sequenz zusammenzuführen).

Der Algorithmus-Implementierungscode lautet wie folgt:

package exp_sort;
public class MergeSort {
  /**
   * 相邻两个有序子序列的合并算法
   *
   * @param src_array
   * @param low
   * @param high
   * @param des_array
   */
  public static void Merge(int src_array[], int low, int high,
      int des_array[]) {
    int mid;
    int i, j, k;
    mid = (low + high) / 2;
    i = low;
    k = 0;
    j = mid + 1;
    // compare two list
    while (i <= mid && j <= high) {
      if (src_array[i] <= src_array[j]) {
        des_array[k] = src_array[i];
        i = i + 1;
      } else {
        des_array[k] = src_array[j];
        j = j + 1;
      }
      k = k + 1;
    }
    // if 1 have,cat
    while (i <= mid) {
      des_array[k] = src_array[i];
      k = k + 1;
      i = i + 1;
    }
    while (j <= high) {
      des_array[k] = src_array[j];
      k = k + 1;
      j = j + 1;
    }
    for (i = 0; i < k; i++) {
      src_array[low + i] = des_array[i];
    }
  }
  /**
   * 2-路归并排序算法，递归实现
   *
   * @param src_array
   * @param low
   * @param high
   * @param des_array
   */
  public static void mergeSort(int src_array[], int low, int high,
      int des_array[]) {
    int mid;
    if (low < high) {
      mid = (low + high) / 2;
      mergeSort(src_array, low, mid, des_array);
      mergeSort(src_array, mid + 1, high, des_array);
      Merge(src_array, low, high, des_array);
    }
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array1[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    int array2[] = new int[array1.length];
    mergeSort(array1, 0, array1.length - 1, array2);
    System.out.println("\n----------after sort-------------");
    for (int ii = 0; ii < array1.length; ii++) {
      System.out.print(array1[ii] + " ");
    }
    System.out.println("\n");
  }
}

Codeerklärung:

Bei der Zusammenführungssortierung erfordert ein Zusammenführungsdurchgang mehrere Aufrufe des 2-Wege-Zusammenführungsalgorithmus. Die Zeitkomplexität eines Zusammenführungsdurchgangs ist offensichtlich linear. Denn es werden höchstens n-1 Vergleiche durchgeführt, wobei n die Gesamtzahl der Elemente ist. Wenn es mehrere Zahlen gibt, das heißt, wenn n nicht 1 ist, führen Sie die erste Hälfte der Daten und die zweite Hälfte der Daten rekursiv zusammen und sortieren Sie sie, um die beiden Teile der sortierten Daten zu erhalten, und führen Sie sie dann zusammen.

Algorithmusanalyse:

Dieser Algorithmus basiert auf der Zusammenführungsoperation (auch Zusammenführungsalgorithmus genannt, der sich auf den Prozess der Kombination von zwei bezieht). sortierte Sequenzen Ein effizienter Sortieralgorithmus, der auf der Operation des Zusammenführens in eine Sequenz basiert. Dieser Algorithmus ist eine sehr typische Anwendung der Divide and Conquer-Methode . Er unterteilt das Problem in einige kleine Probleme und löst sie dann rekursiv. Die Eroberungsphase wird durch Teilen der geteilten Phase gelöst. Jede Antwort passt zusammen; Teilen und Herrschen ist eine sehr wirkungsvolle Anwendung der Rekursion. Hinweis: Im Vergleich zur Schnellsortierung und Heap-Sortierung besteht das größte Merkmal der Zusammenführungssortierung darin, dass es sich um eine stabile Sortiermethode handelt. Die Geschwindigkeit ist nach der schnellen Sortierung an zweiter Stelle und wird im Allgemeinen für Arrays verwendet, die im Allgemeinen ungeordnet sind, deren Unterelemente jedoch relativ geordnet sind.

Komplexität:

Zeitkomplexität ist: O(nlogn) – Dieser Algorithmus ist der beste und effizienteste Schlecht und durchschnittliche Zeitleistung.
Die Raumkomplexität beträgt: O(n)
Die Anzahl der Vergleichsoperationen liegt zwischen (nlogn) / 2 und nlogn - n + 1.
Die Anzahl der Zuweisungsvorgänge beträgt (2nlogn). Die Raumkomplexität des Zusammenführungsalgorithmus beträgt: 0 (n)
Es ist schwierig, ihn für die Hauptspeichersortierung zu verwenden (die Zusammenführungssortierung benötigt mehr Speicher. Das Hauptproblem besteht darin, dass das Zusammenführen zweier sortierter Tabellen linearen zusätzlichen Speicher erfordert, was ebenfalls Kosten verursacht Einige zusätzliche Vorgänge wie das Kopieren von Daten in ein temporäres Array und das anschließende Zurückkopieren verlangsamen die Sortierung erheblich. Dies ist jedoch sehr effizient und wird hauptsächlich für die externe Sortierung und für wichtige Zwecke verwendet Bei internen Sortieranwendungen wählen Sie im Allgemeinen die Schnellsortierung.

Die Schritte für den Zusammenführungsvorgang lauten wie folgt:

Schritt 1: Platz beantragen, sodass seine Größe der Summe aus beiden entspricht sortierte Sequenzen. Der Speicherplatz wird zum Speichern der zusammengeführten Sequenz verwendet. Schritt 2: Setzen Sie zwei Zeiger. Die Anfangspositionen sind die Startpositionen der beiden sortierten Sequenzen. Schritt 3: Vergleichen Sie die Elemente, auf die die beiden Zeiger zeigen. Wählen Sie ein relativ kleines Element aus, platzieren Sie es im Zusammenführungsbereich und bewegen Sie den Zeiger zur nächsten Position.
Wiederholen Sie Schritt 3, bis ein bestimmter Zeiger das Ende der Sequenz erreicht.
Kopieren Sie alle verbleibenden Elemente der anderen Sequenz direkt bis zum Ende der Zusammenführungssequenz

Die Schritte der Zusammenführungssortierung sind wie folgt (vorausgesetzt, dass die Sequenz insgesamt n Elemente hat): Füge alle zwei benachbarten Zahlen in der Sequenz zusammen (merge ), wodurch Floor(n/2)-Sequenzen entstehen. Jede Sequenz enthält nach der Sortierung zwei Elemente.

Füge die obigen Sequenzen erneut zusammen und bilde Floor(n/4)-Sequenzen, jede Sequenz enthält vier Elemente

Wiederholen Sie Schritt 2, bis alle Elemente sortiert sind

[Verwandte Empfehlungen]

1

Java-Datenstruktur-Sortieralgorithmus (1) Baumauswahlsortierung

2.

Ausführliches Tutorial zu Selection Sort_java in Java

3.

Java-Datenstruktur-Sortieralgorithmus (3) Einfache Auswahlsortierung

4. Java-Datenstruktur-Sortieralgorithmus (4) Auswahlsortierung

Das obige ist der detaillierte Inhalt vonJava-Datenstruktur-Sortieralgorithmus (2) Zusammenführungssortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!