Sortieralgorithmus für Java-Datenstrukturen (1) Baumauswahlsortierung

In diesem Artikel wird hauptsächlich der Java-Datenstruktur-Sortieralgorithmus Auswahlsortierung vorgestellt. Er analysiert die Prinzipien, Implementierungstechniken und zugehörigen Vorsichtsmaßnahmen für die Java-Baumauswahlsortierung anhand spezifischer Beispiele Folgendes

Dieser Artikel beschreibt als Beispiel den Java-Datenstruktur-Sortieralgorithmus für die Baumauswahlsortierung. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Hier werden wir über die Sortierung eines der Auswahltypen sprechen: Baumauswahlsortierung

Bei der einfachen Auswahlsortierung wird jeder Vergleich durchgeführt Die Ergebnisse des letzten Vergleichs werden nicht verwendet, daher beträgt die zeitliche Komplexität des Vergleichsvorgangs O(N^2). Wenn Sie die Anzahl der Vergleiche reduzieren möchten, müssen Sie die Größenbeziehung dabei speichern der Vergleichsprozess. Die Baumauswahlsortierung ist eine Verbesserung gegenüber der einfachen Auswahlsortierung.

Baumauswahlsortierung: , auch bekannt als Turnier Sortierung) , ist eine Sortierung, die auf dem Turnierdenken basiert Möglichkeiten zur Auswahlsortierung. Führen Sie zunächst einen paarweisen Vergleich der Schlüsselwörter von n Datensätzen durch, führen Sie dann einen paarweisen Vergleich zwischen den n/2 kleineren durch und wiederholen Sie diesen Vorgang, bis der kleinste Datensatz ausgewählt ist.

Der Algorithmus-Implementierungscode lautet wie folgt:

package exp_sort;
public class TreeSelectSort {
 public static int[] TreeSelectionSort(int[] mData) {
  int TreeLong = mData.length * 4;
  int MinValue = -10000;
  int[] tree = new int[TreeLong]; // 树的大小
  int baseSize;
  int i;
  int n = mData.length;
  int max;
  int maxIndex;
  int treeSize;
  baseSize = 1;
  while (baseSize < n) {
   baseSize *= 2;
  }
  treeSize = baseSize * 2 - 1;
  for (i = 0; i < n; i++) {
   tree[treeSize - i] = mData[i];
  }
  for (; i < baseSize; i++) {
   tree[treeSize - i] = MinValue;
  }
  // 构造一棵树
  for (i = treeSize; i > 1; i -= 2) {
   tree[i / 2] = (tree[i] > tree[i - 1] ? tree[i] : tree[i - 1]);
  }
  n -= 1;
  while (n != -1) {
   max = tree[1];
   mData[n--] = max;
   maxIndex = treeSize;
   while (tree[maxIndex] != max) {
    maxIndex--;
   }
   tree[maxIndex] = MinValue;
   while (maxIndex > 1) {
    if (maxIndex % 2 == 0) {
     tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex + 1] ? tree[maxIndex]
       : tree[maxIndex + 1]);
    } else {
     tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex - 1] ? tree[maxIndex]
       : tree[maxIndex - 1]);
    }
    maxIndex /= 2;
   }
  }
  return mData;
 }
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
  TreeSelectionSort(array);
  for (int i = 0; i < array.length; i++) {
   System.out.print(array[i] + " ");
  }
  System.out.println("\n");
 }
}

Algorithmusanalyse:

Bei der Sortierung der Baumauswahl durchlaufen alle ausgewählten kleinsten Schlüsselwörter einen Vergleichsprozess von Blattknoten zu Folgeknoten. Da ein vollständiger Binärbaum n Blattknoten enthält, beträgt die Tiefe log2n+1 Daher sind bei der Baumauswahlsortierung jedes Mal log2n-Vergleiche erforderlich, sodass die Zeitkomplexität O (nlog2n) beträgt Die Komplexität beträgt O(nlog2n). Im Vergleich zum einfachen Auswahlsortieralgorithmus wird die Anzahl der Vergleiche um eine Größenordnung reduziert und n-1 zusätzlicher Speicherplatz zum Speichern der Zwischenvergleichsergebnisse hinzugefügt.

Ergänzung:

Hier stellen wir einen verbesserten Algorithmus für die Baumauswahlsortierung vor, nämlich den Heap-Sort-Algorithmus.

Heap-Sortierung gleicht den Mangel des Baumauswahl-Sortieralgorithmus aus, der viel Platz beansprucht. Bei Verwendung der Heap-Sortierung ist nur ein Hilfsraum in Datensatzgröße erforderlich.

Die Idee des Algorithmus ist:

Speichern Sie die Schlüsselwörter der zu sortierenden Datensätze im Arrayr[1.. .n] und setze r Es wird als sequentielle Darstellung eines vollständigen Binärbaums betrachtet. Der erste Datensatz r[1] wird als Wurzel des Binärbaums verwendet. 2...n] ist Schicht für Schicht von links nach rechts angeordnet, das linke Kind jedes Knotens r[i] ist r[2*i], das rechte Kind ist r[2*i+1]. ; das übergeordnete Element ist r[[i/2]].

Heap-Definition: Der Schlüsselwert jedes Knotens erfüllt die folgenden Bedingungen:

r[i].key >= r[2i].key und r[ i].key >= r[2i+1].key (i=1,2,...[i/2])

Ein vollständiger Binärbaum, der die oben genannten Bedingungen erfüllt, wird als groß bezeichnet Root-Heap; im Gegenteil, wenn der Schlüssel eines Knotens in diesem vollständigen Binärbaum kleiner oder gleich dem Schlüssel seines linken und rechten Kindes ist, wird der entsprechende Heap als kleiner Root-Heap bezeichnet.

Der Prozess der Heap-Sortierung muss hauptsächlich zwei Probleme lösen: Das erste besteht darin, einen anfänglichen Heap gemäß der Heap-Definition zu erstellen. Das zweite besteht darin, den Heap nach dem Entfernen des größten Elements neu aufzubauen, um das untergrößte zu erhalten Element.

Bei der Heap-Sortierung werden die Eigenschaften des Heaps verwendet, um die Datensatzsequenz zu sortieren:

1. Erstellen Sie einen Heap für die angegebene Sequenz die Oberseite des Heaps; (erste Elementaustausch mit dem Endelement)
3. Erstellen Sie den Heap mit den verbleibenden Elementen neu.
4. Wiederholen Sie die Schritte 2 und 3, bis alle Elemente ausgegeben sind.

Hinweis: „Filtern“ muss beim [n/2]-ten Knoten beginnen und Schicht für Schicht rückwärts bis zum Wurzelknoten vorgehen.

Algorithmusanalyse:

1. Für einen Heap mit einer Tiefe von k beträgt die Anzahl der zum „Filtern“ erforderlichen Schlüsselwortvergleiche höchstens 2(k-1 ) ;

2. Die Heap-Tiefe von n Schlüsselwörtern beträgt [log2n]+1, und die Anzahl der Schlüsselwortvergleiche, die zum anfänglichen Erstellen des Heaps erforderlich sind, beträgt höchstens: n* [log2n];
3 n- 1 Mal überschreitet die Anzahl der erforderlichen Schlüsselwortvergleiche nicht: (n-1)*2 [log2n] Daher beträgt die zeitliche Komplexität der Heap-Sortierung im schlimmsten Fall O(nlog2n). Dies ist der größte Vorteil der Heap-Sortierung.

[Verwandte Empfehlungen]

1. Detailliertes Tutorial zur Auswahlsortierung (Selection Sort_java) in Java

2. Java-Datenstruktursortierung Algorithmus (2) Zusammenführungssortierung

3. Java-Datenstruktur-Sortieralgorithmus (3) Einfache Auswahlsortierung

4 (4) Auswahlsortierung

Das obige ist der detaillierte Inhalt vonSortieralgorithmus für Java-Datenstrukturen (1) Baumauswahlsortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!