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.
2. Java-Datenstruktursortierung Algorithmus (2) Zusammenführungssortierung
3. Java-Datenstruktur-Sortieralgorithmus (3) Einfache 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!
