Der Inhalt dieses Artikels ist: Was ist Heap-Sortierung in Java? Einführung in die Heap-Sortierung. Es hat einen gewissen Referenzwert. Freunde in Not können sich darauf beziehen. Ich hoffe, es wird Ihnen hilfreich sein.
Einführung in die Heap-Sortierung:
Die Heap-Sortierung kann in zwei Stufen unterteilt werden. In der Heap-Konstruktionsphase reorganisieren wir das ursprüngliche Array in einen Heap; in der sinkenden Sortierphase entfernen wir dann alle Elemente der Reihe nach aus dem Heap und erhalten das sortierte Ergebnis.
1. Heap-Konstruktion: Eine effektive Methode besteht darin, die Sink-Funktion von rechts nach links zu verwenden, um den Sub-Heap zu erstellen. Jede Position des Arrays hat einen Wurzelknoten eines Sub-Heaps, und sink() ist auch auf diese Sub-Heaps anwendbar. Wenn sich die beiden untergeordneten Knoten eines Knotens bereits im Heap befinden, wird die Methode sink() aufgerufen Der Knoten kann sie in einem Heap speichern. Wir können den Sub-Heap der Größe 1 überspringen, da für den Sub-Heap der Größe 1 kein sink() erforderlich ist, d.
2. Um den Heap zu sortieren, erstellen wir im ersten Schritt einen Heap. In diesem Heap ist der Wurzelknoten immer der Knoten mit dem maximalen Wert, also tauschen wir den Wert des Wurzelknotens mit dem letzten Wert aus Array. Verwenden Sie einfach sink(), um die Struktur des Heaps beizubehalten.
Spezifische Code-Implementierung:
public class PQSort{
public static void main(String[] args){
int[] a = {9,1,7,5,3,9,12,56,21,45};
sort(a);
for(int i=0;i<a.length system.out.print public int for>=0;k--){
sink(a,k,N);
}
//通过不断把堆中最大值放到数组的后面来排序
while(N>0){
exch(a,0,N--);
sink(a,0,N);
}
}
//下沉函数
private static void sink(int[] a, int i, int n){
while(2*i+1a[j]) break;
exch(a,i,j);
i=j;
}
}
//交换函数
private static void exch(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}</a.length>Laufende Ergebnisse:
Das obige ist der detaillierte Inhalt vonWas ist Heap-Sortierung in Java? Einführung in die Heap-Sortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
