Comment implémenter un algorithme de tri par tas à l'aide de Java

Comment implémenter un algorithme de tri de tas en Java

Le tri de tas est un algorithme de tri basé sur la structure de données de tas, qui tire parti des propriétés du tas pour le tri. Le tri par tas est divisé en deux étapes principales : la création du tas et le tri.

Construire un tas :
Tout d'abord, nous devons construire un grand tas racine ou un petit tas racine en fonction du tableau à trier. Pour le tri ascendant, nous devons créer un grand tas racine ; pour le tri décroissant, nous devons créer un petit tas racine.

La propriété d'un grand tas racine est la suivante : la valeur d'un nœud est supérieure ou égale à la valeur de ses nœuds enfants.
La propriété d'un petit tas racine est : la valeur d'un nœud est inférieure ou égale à la valeur de ses nœuds enfants.

Le processus de construction d'un grand tas racine est le suivant :

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);
    }
}

Tri :
Après avoir construit le grand tas racine, nous devons échanger l'élément supérieur du tas avec le dernier élément du tableau et réduire la portée de le tas, puis effectuez une opération de tas sur le tas, répétez ce processus jusqu'à ce que le tas soit vide. Le tableau final est ordonné.

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);
    }
}

Exemple d'utilisation :

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

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

Le résultat de sortie est : [1, 3, 4, 5, 10], qui est le résultat d'un tri ascendant.

La complexité temporelle du tri par tas est O(nlogn), où n est le nombre d'éléments à trier. Le tri par tas est un algorithme de tri stable adapté au tri de données à grande échelle.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!