|
L'algorithme heapsort est l'un des algorithmes de tri les plus rapides disponibles . Les programmeurs utilisent heapsort en Java parce que c'est un bon choix pour les très grands réseaux qu'ils savent être dans un état non triés. Par souci d'efficacité , la structure réelle de l'arbre n'est pas utilisé. Au lieu de cela , l'arbre est formé en place, à droite dans le tableau. L'algorithme heapsort est «en place» algorithme , car il ne nécessite pas de mémoire supplémentaire pour effectuer le tri . Instructions
1 Compose la méthode de swap. Cela échanger deux éléments d'un tableau "" swap public static void ( int [ ] a, int i , int j) {int tmp = a [ j] ; . Un [j] = a [ i ] , un [i] = tmp ; } ""
2 écrire le noyau de l'algorithme, la méthode de siftDown . Il est utilisé à la fois à la forme de la structure de tas et de faire le tri réelle.
3 Tamiser grandes valeurs vers la racine de l'arbre et des petites valeurs vers les feuilles avec la méthode de siftDown . Comme cette méthode est appelée plusieurs fois pendant le processus de tri , le plus grand nœud est constamment tamisé pour le nœud racine et a déménagé à la fin du tableau . Tout nœud n est jusqu'à deux enfants, dont les indices sont n * 2 + 1 et n * 2 + 2 . "" siftDown public static void ( int [ ] a, int start , int fin ) {int root = commencer , tandis que (racine * 2 + 1 int enfant = racine * 2 + 1; //Si l'enfant a un frère et l' la valeur de l'enfant est inférieure à sa sœur si ( enfant de l'enfant + +; } if ( un swap [ root ] (a, racine , enfant ) ; root = enfant ; } else {return; }} } ""
4 < p> Utiliser la méthode heapify . Cette méthode est appelée au début de la sorte à créer la structure initiale du tas . Cela se fait rapidement , car la structure de tas est un peu vague . la seule exigence est que chaque nœud racine doit être supérieure à la nœuds enfants "" static void heapify publique (int [] a) { for (int start = a.length /2 - 1 ; start> = 0; commencer - ) . siftDown (a, début , a.length -1 ) ; } ""
5 Ecrire la méthode de Heapsort la méthode heapifies premier tableau pour préparer le genre la méthode de siftDown est alors appelé à nouveau depuis le nœud racine est maintenant une faible valeur Ce . . . EIPD une nouvelle grande valeur pour le nœud racine , et l'ensemble du processus est répété jusqu'à ce que la taille du tas est un "" Heapsort public static void (int [] a) { heapify ( a); . for (int fin = a. length - 1 ; end> 1; fin - ) { swap ( a, fin , 0); siftDown (a, 0, fin - 1 );} } ""
6 test . la méthode Heapsort l'exemple suivant montre un petit programme de test "" public static void main ( string [] args) {int [] a = new int [ 10]; . for (int i = 0; i for (int i = 0; i swap ( a, i , i + (int) ( Math.random ( ) * ( 9 - i)) ) ; System.out.println (" Avant le tri :"); for (int i = 0; i Heapsort ( a); System.out.println (" Après le tri "); for (int i = 0; } i ""
|
