So implementieren Sie den Heap-Sortieralgorithmus mit Java

So implementieren Sie den Heap-Sortieralgorithmus in Java

Heap-Sortierung ist ein Sortieralgorithmus, der auf der Heap-Datenstruktur basiert und die Eigenschaften des Heaps zum Sortieren nutzt. Die Heap-Sortierung ist in zwei Hauptschritte unterteilt: Erstellen des Heaps und Sortieren.

Aufbau eines Heaps:
Zuerst müssen wir einen großen Root-Heap oder einen kleinen Root-Heap basierend auf dem zu sortierenden Array erstellen. Für die aufsteigende Sortierung müssen wir einen großen Root-Heap erstellen; für die absteigende Sortierung müssen wir einen kleinen Root-Heap erstellen.

Die Eigenschaft eines großen Root-Heaps ist: Der Wert eines Knotens ist größer oder gleich dem Wert seiner untergeordneten Knoten.
Die Eigenschaft eines kleinen Root-Heaps ist: Der Wert eines Knotens ist kleiner oder gleich dem Wert seiner untergeordneten Knoten.

Der Prozess zum Erstellen eines großen Root-Heaps ist wie folgt:

public static void buildHeap(int[] array, int length) {
    for (int i = length / 2 - 1; i >= 0; i--) {
        heapify(array, length, i);
    }
}

public static void heapify(int[] array, int length, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < length && array[left] > array[largest]) {
        largest = left;
    }

    if (right < length && array[right] > array[largest]) {
        largest = right;
    }

    if (largest != i) {
        int temp = array[i];
        array[i] = array[largest];
        array[largest] = temp;
        heapify(array, length, largest);
    }
}

Sortieren:
Nach dem Erstellen des großen Root-Heaps müssen wir das oberste Element des Heaps mit dem letzten Element des Arrays austauschen und den Umfang reduzieren den Heap und führen Sie dann Heapisierungsvorgänge für den Heap durch. Wiederholen Sie diesen Vorgang, bis der Heap leer ist. Das endgültige Array ist geordnet.

public static void heapSort(int[] array) {
    int length = array.length;

    buildHeap(array, length);

    for (int i = length - 1; i >= 0; i--) {
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;

        heapify(array, i, 0);
    }
}

Verwendungsbeispiel:

public static void main(String[] args) {
    int[] array = {4, 10, 3, 5, 1};
    heapSort(array);

    System.out.println(Arrays.toString(array));
}

Das Ausgabeergebnis ist: [1, 3, 4, 5, 10], was das Ergebnis der aufsteigenden Sortierung ist.

Die zeitliche Komplexität der Heap-Sortierung beträgt O(nlogn), wobei n die Anzahl der zu sortierenden Elemente ist. Heap Sort ist ein stabiler Sortieralgorithmus, der zum Sortieren großer Datenmengen geeignet ist.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie den Heap-Sortieralgorithmus mit Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!